BOJ 백준 3078 : 좋은 친구

시작하면서

　이번 문제는 큐(queue) 문제이다. 큐는 워낙 많이 접하고, 구현해보고, 공부했기 때문에 개념 공부는 따로 글을 올리지 않았다. 바로 문제로 들어가보자.

BOJ 3078 - 좋은 친구

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 3가지이다.

• N : 학생 수

• K : 좋은 친구의 기준이 되는 등수의 차이

• 학생의 이름 글자 길이

　이 문제에서 학생의 이름은 중요하지 않다. 단지 학생의 이름에서 나오는 학생 이름 글자의 “길이”에 대한 정보만이 필요하다.

​

문제 아이디어

　해당 문제를 단순하게 일일이 비교하면 되는지를 먼저 살펴보자. N의 범위는 최대 300,000 이다.

글자 수 길이를 비교할 때 앞에서부터 1, 2, … , N 까지 비교하고 있는 인덱스의 뒷자리 값들과 비교해준다고 하면 다음과 같은 비교 횟수를 진행해야 한다.

• INDEX : 0 - [1, 2, … , N-1] 과 비교
• INDEX : 1 - [2, 3, … , N-1]과 비교

… 이런 식으로 진행하면 대략 O(n^2)의 시간 복잡도를 가진다. 1초에 대략 1억번의 계산을 할 수 있다는 가정하에 최악의 경우를 가정해보면 O(300,000^2) = O(90,000,000,000) = O(900억) => 900초 정도가 걸린다고 가정할 수 있다.

　그러므로 무식하게 모든걸 계산해보는 것은 피하고, 최대한 효율적으로 O(N) 혹은 O(NlogN) 범위 내에서 해결해야한다. (두 범위 모두 1초 이내로 계산 가능)

　나는 다음과 같이 문제를 이해하고 진행했다.

1. 학생들의 이름은 필요없다. 학생들 이름의 “길이” 값만 필요하다.
2. 학생 인덱스로부터 친한 친구 기준인 K를 벗어나는 인덱스끼리는 비교가 불필요하다.
3. 같은 이름의 “길이”를 가진 친구들끼리만 비교하면 된다.

　위와 같이 문제 해결법을 생각했고, 먼저 3. 을 이용하기 위해 큐들을 학생 이름의 길이 2~20글자들로 나누었다. 총 19개의 길이 기준이 있으므로 큐 배열을 [19]로 잡았다.

그 다음 문자열을 받고, 길이에 2를 빼주고(배열이 앞으로 2만큼 땡겨졌으니), 그대로 큐에 넣으면서 좋은 친구의 기준인 K와 비교하는 식으로 풀이를 진행했다.

​

해결

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    queue<int> q[19];
    string name;
    int N = 0, K = 0;
    long long result = 0;

    cin >> N >> K;

    for (int i = 0; i < N; i++)
    {
        cin >> name;

        int nameLength = name.length() - 2;

        while (!q[nameLength].empty())
        {
            int frontValue = q[nameLength].front();

            if (i - frontValue <= K)
            {
                result += q[nameLength].size();
                break;
            }
            else
            {
                q[nameLength].pop();
            }
        }

        q[nameLength].push(i);
    }

    cout << result;

    return 0;
}

​

마치며

　오랜만에 큐에 관련된 문제를 풀었는데 문제의 퀄리티가 좋았고, 난이도도 적당해서 만족스러운 풀이었다. 하지만 코딩 테스트에서 해당 문제가 나왔을 때 자신있게 풀었을지는 의문이다. (시간이 정해진 문제풀이에서는 풀기 전에 어려운 문제는 나중에 진행하므로)

　꾸준히 문제를 풀어가면서 좀 더 자신감을 갖도록 해보자.