[C++] 백준 1655 - 가운데를 말해요

🔐 백준 1655 - 가운데를 말해요

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

🔑 풀이

이 문제에서 주의할 점은 시간 제한이 0.1초로 매우 짧고, 주어지는 입력값이 최대

100000개라는 것이다. 따라서 이 문제를 풀기 위해서는 최소한 $ O (N log N) $ 을 만족해야 한다.

문제에서 요구하는 바는 입력이 주어질 때마다 이제까지의 수 배열 중 중앙값을 출력하는 것이다.

그래서 처음 문제를 접하고 생각한 풀이는 내부적으로 이진 탐색 트리로 구현된 set을

사용하여 이터레이터를 중앙에 맞춰놓은 후 숫자가 들어올 때마다 이터레이터를 움직여 답을

반환하도록 해야겠다는 생각을 했다. 문제를 풀면서 생각했던 알고리즘은 다음과 같다.

인덱스를 중앙에 맞춰놓고 들어오는 숫자에 따라 이터레이터를 움직여 해결

1. 들어오는 숫자가 현재 중앙값보다 작을 때
    1-1 짝수이면 it-- : 중앙값 2개에서 더 작은값으로 이동
    1-2 홀수이면 유지 : 들어오기 전 짝수개였기 때문에 더 작은값의 인덱스 였을 것.
        따라서 작은 수가 들어오면 자동대로 그 수는 중앙값
 
2. 들어오는 숫자가 현재 중앙값보다 클 때
    2-1 짝수이면 유지 : 짝수 개일때는 중앙 두개 중에 작은 수를 반환해야 함. 따라서 유지
    2-2 홀수이면 it++ : 짝수개었기 때문에 중간값으로 가려면 +1

다른 사람의 풀이를 참고하지 않았기에 이 풀이가 최적의 풀이는 절대 아닐 것이다. 실제로

다른 사람의 풀이의 메모리와 시간을 비교해봤을때도 비효율적으로 풀었던 것 같다.

🧩 코드