백준 1655: 가운데를 말해요
https://www.acmicpc.net/problem/1655
문제 설명
숫자를 1개씩 입력으로 주어지는데,
숫자가 주어질 때마다 그 숫자 집합에서 중간값을 출력해야 하는 문제이다.
내 정답 코드
내가 생각한 로직은,
중간에 값을 삽입하기 용이한 자료구조인 리스트를 선언한 뒤,
수 입력이 주어질 때마다 정렬된 리스트에 들어가야 할 인덱스를 찾아 그 위치로 삽입하고
중간값을 출력하는 방식을 생각했다.
삽입 위치를 찾는 방식은 이분탐색을 구현하여 시간복잡도를 줄이고자 했다!
/*
* 숫자가 주어질 때마다 위치 찾아 삽입.
* 삽입 위치 찾는건 이분탐색으로.
* 중간값은 짝수->len/2-1 홀수->len/2
*/
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb;
static int N;
static List<Integer> list;
public static void main(String[] args) throws IOException {
init();
for (int i=0; i<N; i++) {
int newNum = Integer.parseInt(br.readLine());
int targetIdx = binarySearch(0, list.size()-1, newNum);
list.add(targetIdx, newNum);
int midIdx = list.size()/2;
if (list.size()%2 == 0) midIdx -= 1;
sb.append(list.get(midIdx)).append('\n');
}
System.out.println(sb);
}
private static int binarySearch(int s, int e, int target) {
int mid = (s+e)/2;
if (s > e) {
return s;
}
int midNum = list.get(mid);
if (midNum == target) {
return mid;
} else if(midNum < target) {
return binarySearch(mid+1, e, target);
} else {
return binarySearch(s, mid-1, target);
}
}
private static void init() throws IOException {
sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new ArrayList<>();
}
}
결론적으로 정답은 맞았으나, 실행속도가 아쉬웠다.
개선 사항
원인
기존 내 코드의 실행속도가 느렸던 원인을 생각해볼 때,
ArrayList를 사용해 삽입하는 방식이 주요 원인이라고 생각했다.
위 javadoc 내용을 보면 어레이리스트도 결국 배열이기 때문에,
삽입을 하려면 결국 배열처럼 해당 인덱스를 비우기 위해 이후 숫자를 모두 하나씩 미루고,
비워진 자리에 삽입하는 로직이기 때문에 배열 전체를 순회해야 한다.
사실상 시간 복잡도는 O(N2) 인 셈인 것이다.
그래서 대안으로 힙정렬을 생각했다.
PriorityQueue의 정렬방식이기도 한 힙정렬은 시간복잡도가 O(NlogN)으로 더 효율적이다.
개선 코드
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb;
static int N;
static PriorityQueue<Integer> maxHeap; // 최대힙 (작은 수들의 절반)
static PriorityQueue<Integer> minHeap; // 최소힙 (큰 수들의 절반)
public static void main(String[] args) throws IOException {
init();
for (int i = 0; i < N; i++) {
int x = Integer.parseInt(br.readLine());
insert(x);
sb.append(maxHeap.peek()).append('\n'); // 항상 아래 중앙값 출력
}
System.out.print(sb);
}
private static void init() throws IOException {
sb = new StringBuilder();
N = Integer.parseInt(br.readLine().trim());
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
private static void insert(int n) {
// maxheap을 우선으로 담기
if (maxHeap.isEmpty() || n <= maxHeap.peek()) maxHeap.offer(n);
else minHeap.offer(n);
if (maxHeap.size() < minHeap.size()) maxHeap.offer(minHeap.poll());
if (maxHeap.size() > minHeap.size() + 1) minHeap.offer(maxHeap.poll());
if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
int a = maxHeap.poll(), b = minHeap.poll();
maxHeap.offer(b);
minHeap.offer(a);
}
}
}
개선 후 (30% 속도 향상)
배운점
기존에는 매 입력마다 정렬된 리스트에 이분 탐색으로 삽입했는데, 삽입 과정에서 배열의 뒤 원소들을 한 칸씩 밀어야 해서 O(N) 시간이 소요되었다. 따라서 입력이 많아질수록 전체 시간 복잡도가 O(N^2)까지 치솟아 성능상 한계가 있었다.
이를 힙(PriorityQueue) 두 개로 관리하는 방식으로 바꾸면서, 각 입력마다 삽입·삭제 연산을 O(log N)에 처리할 수 있었고, 전체 시간 복잡도는 O(N log N)으로 크게 개선되었다.
다만, 다른 사람들의 200ms대 풀이를 보니 똑같이 힙을 활용하더라도 PriorityQueue 대신 배열 기반으로 직접 힙 연산을 구현해 오버헤드를 줄인 경우가 있었다. 이를 통해 단순히 자료구조를 교체하는 것만으로는 충분하지 않고, 문제 상황에 맞는 세밀한 최적화와 구현 방식의 차이가 성능을 크게 좌우한다는 점을 배울 수 있었다.
