C++로 구현하는 큐의 첫 번째 고유 정수 찾기

문제 소개

정수들이 담긴 큐(queue)가 주어졌을 때, 큐 안에서 가장 앞에 있는 고유한(한 번만 등장하는) 정수를 찾아내는 문제입니다. 이를 위해 FirstUnique 클래스를 구현해야 하며, 클래스는 다음과 같이 동작합니다.

생성자: 큐를 초기화할 숫자 배열을 전달받습니다.
showFirstUnique(): 큐에서 첫 번째 고유한 정수를 반환하며, 존재하지 않으면 -1을 반환합니다.
add(value): 큐에 새로운 값을 추가합니다.

동작 예시

예를 들어 큐를 [2, 3, 5]로 초기화한 뒤 아래와 같이 함수를 호출한다고 가정해 보겠습니다.

showFirstUnique()
add(5)
showFirstUnique()
add(2)
showFirstUnique()
add(3)
showFirstUnique()

이때 출력 결과는 차례대로 2, 2, 3, -1입니다. 처음에는 2가 유일한 값이므로 2가 반환되고, 5를 추가해도 여전히 2가 첫 번째 고유값입니다. 그러나 2를 한 번 더 추가하면 2가 중복되어 3이 첫 번째 고유값이 되고, 마지막으로 3까지 추가하면 모든 값이 중복되므로 -1이 반환됩니다.

풀이 접근 방법

핵심 아이디어는 큐와 빈도 카운트 맵을 함께 사용하는 것입니다. 전체 풀이 과정은 다음과 같습니다.

정수를 저장할 큐 q와 각 값의 등장 횟수를 저장할 맵 cnt를 준비합니다.
생성자: 먼저 nums의 모든 원소 i에 대해 cnt[i]를 1씩 증가시켜 각 값의 등장 횟수를 기록합니다. 이후 다시 nums를 순회하면서 cnt[i]가 1인 원소, 즉 한 번만 등장한 값만 큐 q에 삽입합니다.
showFirstUnique(): 큐가 비어 있지 않고 큐 맨 앞 원소의 등장 횟수가 1보다 큰 동안 계속해서 원소를 제거(pop)합니다. 반복이 끝난 뒤 큐가 비어 있다면 -1을, 그렇지 않다면 맨 앞 원소를 반환합니다.
add(value): cnt[value]를 1 증가시킨 뒤, 그 값이 1이라면(처음 등장한 값이라면) 큐에 삽입합니다.

이 방식의 장점은 showFirstUnique()가 호출될 때마다 이미 중복된 원소들을 큐에서 제거해 주기 때문에, 이후 조회 연산이 분할 상환(amortized) O(1) 시간에 수행된다는 점입니다. 덕분에 데이터가 커져도 효율적으로 동작합니다.

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class FirstUnique {
public:
    queue <int> q;
    map <int, int> cnt;
    FirstUnique(vector<int>& nums) {
        for (int i : nums) {
            cnt[i]++;
        }
        for (int i : nums) {
            if (cnt[i] == 1) {
                q.push(i);
            }
        }
    }
    int showFirstUnique() {
        while (!q.empty() && cnt[q.front()] > 1) q.pop();
        return q.empty() ? -1 : q.front();
    }
    void add(int value) {
        cnt[value]++;
        if (cnt[value] == 1)
            q.push(value);
    }
};
main(){
    vector<int> v = {2,3,5};
    FirstUnique ob(v);
    cout << (ob.showFirstUnique()) << endl;
    ob.add(5);
    cout << (ob.showFirstUnique()) << endl;
    ob.add(2);
    cout << (ob.showFirstUnique()) << endl;
    ob.add(3);
    cout << (ob.showFirstUnique()) << endl;
}

입력

{2,3,5}
ob.showFirstUnique();
ob.add(5);
ob.showFirstUnique();
ob.add(2);
ob.showFirstUnique();
ob.add(3);
ob.showFirstUnique();

출력

마무리

이 문제는 큐의 순서 특성과 해시 맵의 빠른 조회 성능을 결합하면 깔끔하게 해결할 수 있는 대표적인 자료구조 응용 문제입니다. 실무에서도 스트리밍 데이터에서 최초의 비중복 요소를 추적해야 하는 상황에 유사한 패턴이 자주 활용되므로, 큐와 카운트 맵을 조합하는 이 접근 방식을 잘 기억해 두면 유용합니다.