[Algorithm] 1655번: 가운데를 말해요

이 글은 단순히 답을 적은 것이 아닌 답을 도출해내는 과정을 포함한 글입니다.
정답이 아닌 코드가 중간에 포함되어 있으니 정답 코드를 원하시는 분께선 맨 아래쪽으로 스크롤해주시기 바랍니다.

---

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

1655번: 가운데를 말해요

 

문제 설명

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠 때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

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

출력

한 줄에 하나씩 N 줄에 걸쳐 수빈이의 동생이 말해야 하는 수를 순서대로 출력한다.

---

문제 풀이 과정

중간값을 구하기 위해선 여태까지 입력되었던 수들이 정렬되어 있어야 한다.

현재 입력받은 수를 어떻게 정렬된 배열의 정확한 위치에 넣을지가 관건인 것 같다.

 

우선 다음과 같은 알고리즘을 구상해봤다.

1. 리스트를 생성한다.
2. 수를 입력받을 때마다 아래의 동작을 반복한다.
3. 이분 탐색을 통해 입력받은 수가 정렬된 배열의 어디에 삽입되어야 할지 구한다.
4. 배열에 입력받은 수를 삽입한다.
5. 리스트[현재 리스트의 길이 / 2] 값을 출력한다.

입력받은 수 N개에 대해 이분 탐색을 수행하므로 시간 복잡도는 O(nlogn)이 된다.

시간 초과로 통과하지 못할 것 같은 불길한 예감이 들지만 우선 시도라도 해보자.

 

작성한 코드는 다음과 같다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> arrayList = new ArrayList<>();
        int N, num;
        int min, max, index;

        N = sc.nextInt();

        for (int n = 0; n < N; n++) {
            num = sc.nextInt();

            min = 0;
            max = n - 1;

            while(min <= max) {
                index = (min + max) / 2;
                if(arrayList.get(index) < num) {
                    min = index + 1;
                }
                else if(mid > num) {
                    max = index - 1;
                }
                else {
                    min = index;
                    break;
                }
            }

            arrayList.add(min, num);

            //System.out.println(arrayList);
            System.out.println(arrayList.get(n / 2));
        }
    }
}

 

역시 시간 초과가 났다.

 

혹시 Scanner와 System.out.println 함수가 너무 느려서 그런 건가 싶어 BufferedReader, BufferedWriter로 바꿔서 제출해봤다.

 

수정한 코드는 다음과 같다.

주석 처리된 부분이 기존 코드이고, 그 아래 코드가 변경 후 코드이다.

//Scanner sc = new Scanner(System.in);
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

//N = sc.nextInt();
N = Integer.parseInt(bufferedReader.readLine());

//num = sc.nextInt();
num = Integer.parseInt(bufferedReader.readLine());

//System.out.println(arrayList.get(n / 2));
bufferedWriter.write(arrayList.get(n / 2) + "\n");

//추가
bufferedWriter.flush();
bufferedReader.close();
bufferedWriter.close();

 

사실 수정해도 별 차이 없을 거라고 생각했는데 수정하고 제출하니까 예상외로 성공했다.

이게 맞네...

 

문제 풀이에 성공한 후 다른 사람들이 작성한 코드를 보니 내가 해결한 방식인 이분 탐색으로 해결하라고 만든 문제가 아니라 "우선순위 큐"라는 자료구조를 이용하여 푸는 문제라고 한다.

 

우선순위 큐를 사용한 해법 링크

https://yabmoons.tistory.com/478

 

코드를 보니 최대 큐, 최소 큐 2개의 우선순위 큐를 통해 문제를 풀었다.

최대 큐: top에 가장 큰 값이 오며, 중간값과 중간값보다 작은 값들을 포함한다.

최소 큐: top에 가장 작은 값이 오며, 중간값보다 큰 값들을 포함한다.

 

값이 들어올 때마다 최대 큐와 최소 큐에 번갈아가며 저장한다.

저장했을 때 최대 큐의 top보다 최소 큐의 top이 작으면 해당 top 값들을 반대 큐에 저장한다.

 

우선순위 큐이기 때문에 각 큐는 정렬된 상태인 것과 마찬가지이기 때문에 사실상 배열을 반으로 나눠 정렬했다고 생각한다.

 

난 개인적으로 이분 탐색을 통한 풀이가 더 깔끔한 것 같다.

출제자가 의도하지 않은 해법을 찾은 것 같아 기분이 좋다.

---

최종 코드

import java.io.*;
import java.util.ArrayList;

public class Main {

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

        ArrayList<Integer> arrayList = new ArrayList<>();
        int N, num;
        int min, max, index, mid;

        N = Integer.parseInt(bufferedReader.readLine());

        for (int n = 0; n < N; n++) {
            num = Integer.parseInt(bufferedReader.readLine());

            min = 0;
            max = n - 1;

            while(min <= max) {
                index = (min + max) / 2;
                mid = arrayList.get(index);

                if(mid < num) {
                    min = index + 1;
                }
                else if(mid > num) {
                    max = index - 1;
                }
                else {
                    min = index;
                    break;
                }
            }

            arrayList.add(min, num);
            bufferedWriter.write(arrayList.get(n / 2) + "\n");
        }

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

---

질문이나 개선사항은 언제든지 댓글로 남겨주세요.

이상으로 포스팅을 마치겠습니다.