BOJ G2 1655 가운데를 말해요 JAVA

1655번: 가운데를 말해요

---

문제 읽기

맨 처음에 문제를 읽자마자 트리 형태가 먼저 생각났다. 하나씩 숫자를 넣으면서 중간 값을 찾아낼 수 있지 않을까 하는 생각. 하지만 자료구조를 본 게 시간이 좀 지나서 어떤 식으로 구현해야 할 지는 감이 잘 잡히지 않았다.

 

그 다음 생각난 접근은 정렬이다. 하나씩 값이 들어오고, 값이 몇 개 들어왔는지 알 수 있고.. 그렇다면 삽입 정렬을 하면 되지 않을까 싶었다. 하지만 삽입 정렬의 시간복잡도는 최악의 경우 N^2이기 때문에(문제에서 N은 10만) 단순하게 구현하면 시간 초과가 날 것 같았다.

 

그래서 삽입 정렬 + 이진 탐색을 생각했다.

 

💡 삽입 정렬

새로운 원소(N)가 들어왔을 때, 정렬된 배열에서 새로운 원소가 삽입될 자리를 찾아(N) 그 위치에 새로운 원소를 삽입한다.

 

위에서 각각 새로운 원소 N개마다 자리를 찾는 데 걸리는 시간이 N이기 때문에 최악의 경우 N^2의 시간 복잡도가 나온다. 따라서 시간 복잡도를 줄이기만 한다면 이 방법도 가능하지 않을까 생각했고, 새로운 원소가 삽입될 자리를 찾는 것을 Linear한 탐색이 아닌 이분 탐색으로 변경하였다.

 

그렇게 되면 최종적으로 최악의 경우 NlogN의 시간복잡도가 된다.

---

문제 풀기

삽입 정렬 + 이진 탐색

1. 새로운 원소가 들어온다
2. 정렬된 배열에서 새로운 원소가 들어갈 자리를 이진 탐색을 통해 찾는다
3. 해당 위치에 새로운 원소를 삽입한다
4. 중간값을 반환한다.

풀이는 코드로 보면 바로 이해할 수 있을 것 같다.

package ps.dataStructure;

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

public class BOJ_G2_1655_가운데를_말해요 {

    static ArrayList<Integer> nums;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(in.readLine());
        nums = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++){
            int number = Integer.parseInt(in.readLine());
            insertionSort(number, i);
            sb.append(nums.get((i == 0)? 0 : i / 2)).append("\\n");
        }
        System.out.println(sb);
    }

    private static void insertionSort(int number, int i) {
        //1. 이분탐색
        int idx = binarySearch(number, 0, i);
//        System.out.println(idx);

        //2. 해당 위치에 삽입
        nums.add(idx, number);
//        System.out.println(nums);
    }

    private static int binarySearch(int number, int start, int end){
//        System.out.println(start + " " + end);
        if (start >= end) return end;

        int mid = (start + end) / 2;
        if (number <= nums.get(mid)){
            end = mid;
        }
        else{
            start = mid+1; //+1을 뺴먹으면 무한루프
        }
        return binarySearch(number, start, end);
    }
}

 

정답이다.

하지만 속도가 마음에 들지 않았다.

다른 사람들이 한 채점 결과를 보면 C++은 28ms..에서도 끊기고 자바도 400, 500ms 정도였다. 그리고 문제의 유형을 보니 우선순위 큐였다. 그래서 질문 게시판을 참고해서 다른 방식이 뭔지 찾아봤다.

 

---

우선순위 큐, 최대 힙과 최소 힙

글 읽기 - 이 문제는 어떻게 풀어야 되는 걸까요~~..ㅠㅠ

위 글을 보고 중앙값을 기준으로 큰 값과 작은 값을 두 개의 큐로 관리하는 방법이 있는 것을 알았고, 이 방식으로도 풀어보기로 했다.

1. 중앙값 변수, 중앙값보다 작은 수를 저장할 minHeap, 중앙값보다 큰 수를 저장할 maxHeap을 선언한다. 중앙값은 초기 값으로 -10001으로 초기화한다.
2. 맨 처음 값이거나, 중앙값보다 작거나 같으면 minHeap, 중앙값보다 크면 maxHeap에 넣는다.
3. i가 짝수라면 원소의 총 개수는 홀수이고, i가 홀수라면 원소의 총 개수는 짝수이다.
   1. 따라서 원소가 홀수라면 minHeap에 원소를 하나 더 넣어 minHeap에서 peek한 값이 중앙값이 된다.
   2. 원소가 짝수라면 minHeap과 maxHeap의 크기를 같게 만들어 minHeap에서 peek한 값이 중앙값이 된다.
4. 중앙값 변수도 업데이트하고 다음 루프를 돈다

package ps.dataStructure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class BOJ_G2_1655_가운데를_말해요_ver2 {
    //작은 수를 저장하는 PQ - 높은 값이 먼저 나옴
    static Queue<Integer> minQ = new PriorityQueue<>(Collections.reverseOrder());
    //큰 수를 저장하는 PQ
    static Queue<Integer> maxQ = new PriorityQueue<>();
    static int midNum = -10001;

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

        int N = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++){
            int num = Integer.parseInt(in.readLine());

            //Q에 삽입
            if (midNum == -10001 || midNum >= num){
                minQ.add(num);
            }
            else {
                maxQ.add(num);
            }

            //Q 업데이트
            while(true){
                if (
                        i%2 != 0 && (minQ.size() == maxQ.size()) ||
                        i%2 == 0 && (minQ.size() == maxQ.size() + 1)
                ) break;
                if (minQ.size() > maxQ.size()){
                    maxQ.add(minQ.poll());
                }
                else{
                    minQ.add(maxQ.poll());
                }
            }

            midNum = minQ.peek();
            sb.append(midNum).append("\\n");
        }
        System.out.println(sb);
    }

}

 

 

이 코드는 속도가 거의 1/3로 줄어들었다.

정답이 나오더라도, 상황에 맞는 자료구조를 사용하는 것 또한 중요하다는 것을 깨달았다.