ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Java 1655 가운데를 말해요
    PS 2023. 8. 25. 10:25

     

    https://www.acmicpc.net/problem/1655

     

    1655번: 가운데를 말해요

    첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1

    www.acmicpc.net

     


    시간 제한이 0.1초이기에 원소가 들어올 때 마다 중간값을 찾는다면 시간초과가 날 것이다.(N이 최대 100,000이기 때문에)

    그래서 우선순위 큐를 두개를 사용하여 해당 문제를 풀이하였다.

     

    문제의 예시처럼 1, 5, 2 10, -99, 7, 5 가 입력 값으로 주어질 때 원소 하나당 어떤 작업이 이루어지는지 살펴보겠다.

     

    우선 1이 들어올 때 모든 큐에 값이 없으므로 maxHeap에 원소를 넣어준다 그럼 큐 두개의 상태는 아래와 같다.

    1번째 원소가 들어온 뒤 - maxHeap : 1, minHeap : X;

    2번째 원소가 들어온 뒤 - maxHeap : 1, minHeap : 5;

    3번째 원소가 들어온 뒤 - maxHeap : 1,2 minHeap : 5;

     

    이때 maxHeap의 peek한 값과 minHeap의 peek한 값을 비교하여 maxHeap과 minHeap의 스왑이 일어난다.

    이 과정을 거치면 두 큐에 원소가 제대로 삽입되었기에 maxHeap의 값을 peek하여 출력한다.

     

    우선순위 조건이 서로 다른 두개의 큐를 사용한다면 낮은 수부터 높은 수까지 정렬된 상태로 가운데에서 원소의 접근에 걸리는 시간복잡도가 상수시간이기 때문에 해당 문제를 풀이할 수 있었다.

     


    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.io.IOException;
    import java.util.*;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
    
            StringBuilder sb = new StringBuilder();
    
            PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    
            for(int i = 0; i < n; i++){
                int num = Integer.parseInt(br.readLine());
                if(maxHeap.size() == minHeap.size()){
                    maxHeap.add(num);
                }else {
                    minHeap.add(num);
                }
                if(!maxHeap.isEmpty() && !minHeap.isEmpty()) {
                    if (maxHeap.peek() > minHeap.peek()) {
                        int tmp = minHeap.poll();
                        minHeap.add(maxHeap.poll());
                        maxHeap.add(tmp);
                    }
                }
                sb.append(maxHeap.peek()).append("\n");
            }
    
            System.out.println(sb);
        }
    }

    'PS' 카테고리의 다른 글

    Java 1654 랜선 자르기  (0) 2023.08.29
    Java 11967 불켜기  (0) 2023.08.25
    Java 2636 치즈  (0) 2023.08.22
    Java 1976 여행 가자  (0) 2023.08.11
    Java 11404 플로이드  (0) 2023.08.08
Designed by Tistory.