[백준] 13144 List of Unique Numbers (C++)

링크: https://www.acmicpc.net/problem/13144

문제

길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

출력

조건을 만족하는 경우의 수를 출력한다.

---

풀이

굉장히 간단하면서 까다로운 문제이다.

만약 10만개의 수에 대하여 1~10만개의 집합을 일일히 구하면 10만*10만으로 시간 초과가 발생할 것이다.

 

그렇기에 큐를 통해 숫자들이 중복하지 않도록 유지하며 O(n)으로 문제를 풀어야 한다. (투 포인터도 가능)

예시 1 2 3 1 2를 통해 접근해보자.

 

단계 1

큐: ( )

숫자: 1

 

큐가 비어있는 상태에서 1이 들어왔다. 1을 추가해주자.

 

단계 2

큐: (1)

숫자: 2

 

큐에 있는 수와 숫자 2가 중복되지 않는다.

숫자 2는 큐에 있는 수 1과 함께 (1, 2) 집합을 만들 수 있으므로 답에 1을 더한다.

마지막으로 큐에 숫자2를 추가해주자.

 

단계 3

큐: (1, 2)

숫자: 3

 

큐에 있는 수와 숫자 3이 중복되지 않는다.

숫자 3은 큐에 있는 수 1, 2와 함께 (1, 2, 3), (2, 3) 집합을 만들 수 있으므로 답에 2를 더한다.

마지막으로 큐에 숫자 3을 추가해주자.

 

단계 4

큐: (1, 2, 3)

숫자: 1

 

큐에 있는 수 1과 숫자 1이 중복된다. 따라서 중복되는 수 1이 제거될 때 까지 큐를 pop해준다.

이 때 큐는 (2, 3)이 될 것이고, 숫자 1과 함께 (2, 3, 1), (3, 1) 집합을 만들 수 있으므로 답에 2를 더한다.

마지막으로 큐에 숫자 1을 추가해주자.

 

단계 5

큐: (2, 3, 1)

숫자: 2

 

큐에 있는 수 2와 숫자 2가 중복된다. 따라서 중복되는 수 2가 제거될 때 까지 큐를 pop해준다.

이 때 큐는 (3, 1)이 될 것이고, 숫자 2과 함께 (2, 3, 1), (3, 1) 집합을 만들 수 있으므로 답에 2를 더한다.

마지막으로 큐에 숫자 2를 추가해주자.

 

단계 6

지금까지 구한 모든 경우의 수는 집합의 크기가 2 이상인 경우였다.

집합의 크기가 1인 경우도 답에 포함되므로, 답에 숫자의 개수인 5를 더한다.

 

따라서 최종적으로 답은 1 + 2 + 2 + 2 + 5 = 12이다.

 

참고로, 숫자 i가 들어왔을 때 이를 포함하여 만들 수 있는 크기가 2 이상인 집합은 "큐의 사이즈"와 같다.

그리고 답이 int범위를 넘어서는 것을 유의하면 정답을 구해낼 수 있다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

bool visited[100001];

int main(){
    int N;
    cin >> N;

    long long answer = 0;
    queue<int> q;

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

        if (!visited[a]){
            visited[a] = true;
            answer += q.size();
        }
        else{
            while (q.front() != a){
                visited[q.front()] = false;
                q.pop();
            }
            q.pop();

            answer += q.size();
        }
        
        q.push(a);
    }

    cout << answer + N;
}