[백준] 1655번 가운데를 말해요 문제풀이 feat.자바 JAVA

 

[백준] 1655번 가운데를 말해요 문제풀이 feat.자바 JAVA

문제

 

문제풀이방법

문제에서 요구하는 것은 수빈이가 어떤 수를 말할 때마다 그 수들의 가운데 있는 수를 찾아서 말하는 것이다.

 

그렇다면 어떻게 해야할까?

1. 단순히 생각했을 때, 입력값들을 저장해놓고 정렬을 한 후에, 가운데 있는 값을 찾아주면 된다. 

   - 하지만, N의 범위가 100,000이고, 매번 정렬을 하는 것의 시간복잡도는 O(NlogN)

   -> 그러므로 총 시간복잡도는 N*N*logN이 될 것이고 시간초과 다.

 

2. 입력한 값 중에 중간 값들을 기억하고 있으면 어떨까?

   - 입력한 값의 작은값을 담는 공간 하나와, 큰 값들을 담는 공간 하나, 총 2개의 공간을 만들어 놓고, 두개의 공간에는 데이터의 수가 일정하게 유지시키면서 작은 값을 출력하면 된다. 

     - 왜 더 작은숫자인가?

        -> 문제에서 제시하고 있는 곳을 보면 짝수개라면 중간에 있는 두 수 중 작은 수를 말해야 한다고 했기 때문에

 

 

 

 

그림으로 봐보자!

 

1. 값이 큰 것이 우선인 최대힙, PQ와 값이 작은 것이 우선인 최소힙, PQ 가 필요하다.

2. 수빈이가 1을 말했다. 

   최대힙에 1이 들어갈 것이다. 

   그 이유는, 무조건 최대힙의 peek값을 꺼내서 출력하기 위함이다.

   즉, 최대힙과 최소힙의 크기가 같을 경우는 무조건 최대힙에 값을 넣겠다. 

 

3. 그 다음으로 5를 말했다.

   - 우리는 항상, 최대힙과 최소힙에 들어있는 크기를 맞추기 위해서 같지 않는 경우는 최대힙이 항상 크기 때문에 최소힙에 값을 넣어준다. 

   - 최대힙의 peek()값 < 최소힙의 peek() 값이 성립하기 때문에 별다른 일이 일어나지 않고 넘어간다. 

4. 다음으로 2이다. 

   - 최대힙으로 정렬되어 2가 peek가 될것이다.

   - 최대힙의 peek()값 < 최소힙의 peek() 값이 성립하기 때문에 별다른 일이 일어나지 않고 넘어간다. 

5. 다음으로 10

 

6. 다음으로 -99

 

7. 다음은 7

8. 다음은 5

9. 이런식으로 진행이 될 것이다.

  - 만약, 최대힙의 peek()값 < 최소힙의 peek() 값이 성립하지 않는다면, 최대힙의 peek() 와 최소힙의 peek() 부분을 바꿔줘야한다!

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class SayMiddle_1655 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minPQ = new PriorityQueue<>();

        for(int i=0; i<N; i++) {
            int a = Integer.parseInt(br.readLine());

            if(maxPQ.size() == minPQ.size()) {
                maxPQ.add(a);

                if(!minPQ.isEmpty() && maxPQ.peek() > minPQ.peek()) {
                    minPQ.add(maxPQ.poll());
                    maxPQ.add(minPQ.poll());
                }
            }
            else {
                minPQ.add(a);

                if(maxPQ.peek() > minPQ.peek()) {
                    minPQ.add(maxPQ.poll());
                    maxPQ.add(minPQ.poll());
                }
            }

            System.out.println(maxPQ.peek());
        }
    }
}

 

 

문제링크

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요