[레벨 1] 프로그래머스 오늘의 문제 : 명예의 전당 (1) - Priority Queue로 Top-K 관리하기

문제풀이 시간 : 20분

오늘의 코테 연습문제는 프로그래머스의
명예의 전당 (1) 문제다.

문제 링크는 아래와 같다.

https://school.programmers.co.kr/learn/courses/30/lessons/138477?language=cpp

---

문제 설명

"명예의 전당"이라는 TV 프로그램에서는 매일 한 명의 가수가 노래를 부르고,
시청자들의 문자 투표수에 따라 점수를 받는다.

매일 새로운 점수가 들어왔을 때
지금까지 등장한 점수 중 상위 K개의 점수만 명예의 전당에 유지한다.

그리고 매일 발표해야 하는 값은

현재 명예의 전당에 올라가 있는 점수들 중 가장 낮은 점수

다.

예를 들어

k = 3

score = [10, 100, 20, 150, 1, 100, 200]

라면 매일 발표되는 점수는

[10, 10, 10, 20, 20, 100, 100]

이 된다.

---

제한 사항

3 ≤ k ≤ 100

7 ≤ score의 길이 ≤ 1,000

0 ≤ score[i] ≤ 2,000

---

처음 문제를 봤을 때

문제를 읽고

"이거 생각보다 너무 쉬운데?"

라는 생각이 들었다.

처음에는 queue, priority_queue가 바로 떠올랐다.

그런데 문제의 입력 크기를 보니
일반 vector를 이용해서 정렬해도 충분히 풀 수 있겠다는 생각이 들었다.

문제를 다시 아주 단순하게 정리하면 다음과 같다.

매일 지금까지 나온 점수 중 상위 K개를 기준으로,
그 K개 중 가장 낮은 점수를 출력하라.

처음 K명이 다 차기 전까지는
지금까지 등장한 점수 중 최솟값을 출력하면 된다.

현재까지 나온 사람 수 ≤ K
→ 지금까지 점수 중 최솟값

그리고 K명보다 많은 사람이 등장한 이후부터는
전체 점수를 오름차순으로 정렬했을 때

rank.size() - k

번째 원소가 현재 상위 K개 중 가장 작은 점수가 된다.

예를 들어

score = [10, 20, 100, 150]

정렬 후
[10, 20, 100, 150]

k = 3

이라면 상위 3개는

20, 100, 150

이고,

rank.size() - k

= 4 - 3
= 1

이므로

rank[1] = 20

을 출력하면 된다.

아이디어는 단순했다.

곧바로 구현에 들어갔다.

---

나의 풀이

#include <bits/stdc++.h> 
using namespace std;

vector<int> solution(int k, vector<int> score) { 
    // 명예의 전당 목록의 점수의 개수 K,
    // 1일부터 마지막 날까지 출연한 가수들의 점수인 score,
    // 결과물은 그 날의 가장 최하위 점수
    vector<int> answer;

    // 1단계: 먼저 rank 라는 vector를 만든다.
    // 그리고 K보다 작을 경우의 로직까지 설계 (가장 최하위만 return)
    vector<int> rank; 

    for (int x : score) {

        rank.push_back(x); // score에 있는 숫자를 rank로 하나씩 넣은 후
        sort(rank.begin(), rank.end()); // 정렬까지 맡는다

        // case 1) : k보다 작을 때는 그냥 sort로 정렬 후
        // 0번째에 있는 숫자를 넣으면 간단
        if (rank.size() <= k) {
            answer.push_back(rank[0]); 
            continue; 
        }

        // case 2) : 현재 rank는 오름차순으로 정렬되어 있음.
        // 즉 rank.size() - k 위치가
        // 현재 상위 k개의 점수 중 가장 작은 숫자임
        answer.push_back(rank[rank.size() - k]);    
    }

    return answer;
}

---

결과는?

정답이었다.

생각보다 쉽게 풀려서 조금 당황했지만...

그래... 이게 레벨 1이지...

라는 생각도 들었다.

하지만 문제를 맞히고 나서 코드를 다시 보니
효율성 측면에서는 꽤 아쉬운 부분이 있었다.

---

문제는 매번 정렬한다는 것

핵심은 이 부분이다.

for (int x : score) {

    rank.push_back(x);
    sort(rank.begin(), rank.end());

매일 새로운 점수가 하나 들어올 때마다
rank 전체를 다시 정렬하고 있다.

예를 들어 점수가 총 N개라면
정렬되는 배열의 크기는 다음처럼 증가한다.

1개 정렬
2개 정렬
3개 정렬
...
N개 정렬

각 정렬 비용은 대략

1 log 1
2 log 2
3 log 3
...
N log N

이 된다.

따라서 전체 연산량은

Σ i log i

형태가 되고,

Big-O로 보면 대략

O(N² log N)

으로 볼 수 있다.

물론 이 문제에서는

N ≤ 1,000

이라 충분히 통과한다.

하지만 생각해보면 조금 이상하다.

문제에서 우리가 실제로 필요한 것은

지금까지 등장한 모든 점수

가 아니다.

필요한 것은 오직

현재 상위 K개의 점수

뿐이다.

즉 굳이 모든 점수를 계속 저장하고
매번 전체를 다시 정렬할 필요가 없는 것이다.

---

더 나은 자료구조는 없을까?

여기서 처음 문제를 읽었을 때 떠올렸던
Priority Queue가 다시 등장한다.

우선순위 큐는 일반 Queue처럼

먼저 들어온 값

을 먼저 꺼내는 것이 아니라,

우선순위가 가장 높은 값

을 먼저 꺼낼 수 있는 자료구조다.

C++의 priority_queue는 기본적으로 Max Heap으로 동작한다.

priority_queue<int> pq;

즉 가장 큰 값이 top()에 위치한다.

하지만 이번 문제에서는
명예의 전당 상위 K명 중

가장 작은 점수

를 계속 알아야 한다.

따라서 필요한 것은 Min Heap이다.

---

왜 Min Heap이 필요한가?

명예의 전당에 다음 점수들이 있다고 해보자.

20
100
150

여기서 우리가 매일 발표해야 하는 점수는

20

이다.

그리고 새로운 점수

200

이 들어오면

20
100
150
200

중 상위 3명만 남겨야 한다.

즉 가장 작은 값인

20

을 제거하면 된다.

결과는

100
150
200

이다.

다시 말하면 매번 필요한 연산은

현재 상위 K개 중 최솟값 확인
↓
새로운 점수가 들어옴
↓
K개를 초과하면 최솟값 제거

이다.

이 구조는 Min Heap과 정확히 맞는다.

---

C++에서 Min Heap 만들기

C++에서는 다음처럼 작성할 수 있다.

priority_queue<int, vector<int>, greater<int>> rank;

처음 보면 굉장히 복잡해 보인다.

하나씩 뜯어보자.

int
→ 저장할 자료형

vector<int>
→ 내부적으로 데이터를 저장할 Container

greater<int>
→ 작은 값을 더 높은 우선순위로 두는 비교 기준

즉,

priority_queue<int, vector<int>, greater<int>>

는

int 값을 저장하고, 가장 작은 값을 top()에서 바로 꺼낼 수 있는 Priority Queue

라고 보면 된다.

---

Priority Queue를 활용한 풀이

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;

    priority_queue<int, vector<int>, greater<int>> rank;

    for (int x : score) {

        rank.push(x);

        if (rank.size() > k) {
            rank.pop();
        }

        answer.push_back(rank.top());
    }

    return answer;
}

처음 내 코드보다 훨씬 짧아졌다.

---

코드 흐름을 하나씩 살펴보자

먼저 Min Heap을 만든다.

priority_queue<int, vector<int>, greater<int>> rank;

그리고 하루의 점수를 하나씩 넣는다.

rank.push(x);

아직 K명이 다 차지 않았다면
그냥 계속 넣으면 된다.

예를 들어

k = 3

10 입력
→ [10]

100 입력
→ [10, 100]

20 입력
→ [10, 20, 100]

Min Heap의 top()에는 항상
현재 가장 작은 값이 존재한다.

따라서

rank.top();

을 그대로 발표하면 된다.

---

K개를 초과하면?

새로운 점수를 넣은 뒤

if (rank.size() > k) {
    rank.pop();
}

을 수행한다.

Min Heap에서는 pop()을 하면
가장 작은 값이 제거된다.

예를 들어

현재 명예의 전당

10
20
100

에

150

이 들어온다고 해보자.

우선 넣는다.

10
20
100
150

크기가 k = 3을 초과했으므로

rank.pop();

을 수행한다.

그러면 가장 작은

10

이 제거된다.

결과적으로

20
100
150

만 남는다.

정확히 상위 3개의 점수만 유지되는 것이다.

---

현재 최하위 점수는?

Min Heap에는 항상 상위 K개의 점수만 남아 있다.

그리고 그중 가장 작은 값은

rank.top()

이다.

따라서 매일

answer.push_back(rank.top());

만 하면 된다.

정말 문제의 요구사항과 자료구조의 특성이 정확하게 맞아떨어진다.

---

두 풀이의 차이를 비교해보자

내 첫 번째 풀이는

지금까지의 모든 점수를 저장
↓
매번 전체 정렬
↓
상위 K번째 위치 확인

이었다.

반면 Priority Queue 풀이는

상위 K개의 점수만 저장
↓
가장 작은 점수는 항상 top()
↓
K개를 넘으면 가장 작은 값 제거

이다.

구조 자체가 훨씬 문제의 요구사항에 가깝다.

---

시간복잡도 비교

첫 번째 풀이

매번 커지는 전체 배열을 다시 정렬한다.

O(N² log N)

정도로 볼 수 있다.

Priority Queue 풀이

Heap에는 최대 K개의 원소만 존재한다.

push()와 pop()은 각각

O(log K)

이다.

이를 N개의 점수에 대해 반복하므로

O(N log K)

가 된다.

그리고 Heap의 크기도 최대 K이므로
공간복잡도는

O(K)

이다.

첫 번째 풀이는 모든 점수를 저장하기 때문에
공간은

O(N)

이 필요하다.

---

여기서 한 가지 중요한 점

처음에는

"내 코드도 결국 score를 한 번 순회하니까 O(score.size()) 정도 아닌가?"

라고 생각할 수 있다.

하지만 반복문이 한 번 있다고 해서 무조건 O(N)은 아니다.

반복문 안에서 어떤 연산을 하는지도 봐야 한다.

내 코드에서는 매 반복마다

sort(rank.begin(), rank.end());

가 실행된다.

sort() 자체가 배열 크기 M에 대해

O(M log M)

의 시간이 필요하다.

그리고 M이

1, 2, 3, ..., N

으로 계속 커진다.

따라서 단순한

O(N)

순회라고 볼 수 없다.

이번 문제에서 개인적으로 가장 다시 기억해둘 만한 부분이었다.

---

사실 내 첫 번째 풀이도 실전에서는 나쁘지 않다

그렇다고 첫 번째 풀이가 잘못된 풀이는 아니다.

문제의 제한을 보면

score.size() ≤ 1,000

이다.

따라서 매번 정렬하더라도 충분히 빠르게 통과한다.

코딩테스트에서 가장 중요한 것은 우선

정확하게 풀리는 코드를 제한 시간 안에 작성하는 것

이다.

처음부터 항상 가장 최적화된 풀이만 찾으려고 하다가
문제 자체를 못 푸는 것보다는

1. 먼저 확실한 풀이를 구현한다.
2. 시간복잡도를 확인한다.
3. 필요하다면 더 적절한 자료구조로 개선한다.

라는 접근이 실전에서는 훨씬 현실적이라고 생각한다.

이번에도 내가 처음 떠올린 vector + sort 방식으로
문제를 먼저 해결한 뒤,

"현재 상위 K개만 유지하면 되는데 왜 전체 데이터를 정렬하고 있지?"

라는 질문을 통해 Priority Queue 풀이로 개선할 수 있었다.

---

문제를 풀고 나서

처음 문제를 읽었을 때는 생각보다 너무 간단해서
그냥 배열을 이용해 바로 풀었다.

실제로 제한사항만 본다면
내 풀이도 충분히 통과하는 코드였다.

하지만 문제를 풀고 나서 다시 보니
이 문제는 Priority Queue를 연습하기 정말 좋은 문제였다.

핵심은 이것이다.

상위 K개만 유지한다.

그리고 그 K개 중
가장 작은 값이 계속 필요하다.

이 문장을 보는 순간

Min Heap

을 떠올릴 수 있어야 한다.

---

결론

이번 문제를 통해 가져갈 핵심은 크게 세 가지다.

1. 먼저 단순한 풀이로 문제를 해결하는 것도 충분히 좋은 접근이다.

2. 반복문 안에서 sort()를 수행한다면
   단순히 O(N)이라고 생각하면 안 된다.

3. "상위 K개를 계속 유지하면서 그중 최솟값이 필요하다"
   는 문제에서는 Min Heap을 떠올릴 수 있다.

특히 Priority Queue 풀이의 시간복잡도는

O(N log K)

이고,

내 첫 번째 vector + sort 풀이보다
문제의 구조 자체를 훨씬 직접적으로 표현한다.

처음 문제를 풀 때

queue?
priority_queue?
vector?

를 고민하다가 가장 익숙한 vector로 풀었는데,
결과적으로는 Priority Queue를 다시 공부할 좋은 계기가 됐다.

앞으로 코딩테스트에서

최댓값 또는 최솟값을 계속 꺼내야 한다.

상위 K개 또는 하위 K개만 유지해야 한다.

값이 계속 들어오는데 매번 전체 정렬하기에는 비효율적이다.

라는 조건이 보이면
Priority Queue를 먼저 떠올려봐야겠다.