[백준 1655] 가운데를 말해요 (Java)

문제

 

풀이

우선순위 큐로 푸는게 좋다.

아래 코드는 우선순위 큐로 풀지 않은 시간초과 코드이다.

반복문을 돌때마다 sort 하였기에 시간초과가 발생하였다. (틀린코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int totalNum = 0;
    static List<Integer> subinNumList = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        // 수빈이가 외치는 정수의 개수
        totalNum = Integer.parseInt(br.readLine());

        int middleVal = 0;
        while(totalNum-- > 0) {
            subinNumList.add(Integer.parseInt(br.readLine()));  // 정수 입력
            subinNumList.sort(null);

            int curLength = subinNumList.size();    // 현재 리스트 사이즈
            int middleIdx = curLength / 2;          // 현재 중간 인덱스
            if (curLength % 2 == 0)
                middleVal = subinNumList.get(middleIdx) >= subinNumList.get(middleIdx-1)
                        ? subinNumList.get(middleIdx-1)
                        : subinNumList.get(middleIdx);
            else
                middleVal = subinNumList.get(middleIdx);

            System.out.println(middleVal);
        }
    }
}

 

---

잠시, 우선순위 큐란 무엇일까 ?

일반적인 Queue 와 달리, 들어가는 순서는 상관없다. 규칙이 중요하다.

규칙에 따라 우선순위가 정해지고, 우선순위가 가장 높은 데이터가 가장 먼저 나오는 구조이다.

큐와 동일하게 add(), poll(), peek() 메소드를 사용할 수 있다. (add 와 offer 는 같은 기능의 메소드)

---

정답 코드