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

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

13144번: List of Unique Numbers

---

List of Unique Numbers 문제는 투 포인터로 해결할 수 있습니다.

 

중복이 없는 수열의 시작점을 st, 끝점을 en라고 하겠습니다.

 

따라서, st + 1부터 en까지도 중복이 없습니다.

하지만, seq[st]를 제외하였으므로, en을 이동시켜 중복이 없는 수열의 끝점을 다시 찾아야합니다. 

(단, seq는 입력 받은 수열을 의미함)

 

seq = {1, 2, 3, 1, 2}로 예를 들어보겠습니다.

idx	0	1	2	3	4
seq[idx]	1	2	3	1	2

중복이 없는 시작점과 끝점을 구하는 과정은 아래와 같습니다. 

1. st = 0, en = 0, ans = 0;
2. en을 이동시켜, 중복이 없는 수열의 끝점을 찾는다. 그 결과로 st = 0, en = 2가 된다. 
3. st를 한 칸 이동시킨다. st = 1, en = 2
4. en을 이동 시켜, 중복이 없는 수열의 끝점을 찾는다. 그 결과로 st = 1, en = 3이 된다. 
5. st를 한 칸 이동시킨다. st = 2, en = 3
6. en을 이동 시켜, 중복이 없는 수열의 끝점을 찾는다. 그 결과로 st = 2, en = 4이 된다.
7. st를 한 칸 이동시킨다. st = 3, en = 4
8. en을 이동 시켜, 중복이 없는 수열의 끝점을 찾는다. 그 결과로 st = 3, en = 4이 된다.
9. st를 한 칸 이동시킨다. st = 4, en = 4

중복이 없는 수열의 길이는 en - st + 1이고, 수열의 길이가 X일 때, st가 시작점인 연속 수열의 개수는 X개입니다.

예를 들어 seq = {1, 2, 3, 4}에서 만들 수 있는 수열은 아래와 같습니다.

1
1 2
1 2 3
1 2 3 4

따라서, seq = {1, 2, 3, 1, 2}의 예에서 만들 수 있는 수열의 개수는 12개(3 + 3 + 3 + 2 + 1)입니다.

 

⚠️ 단, 길이가 100,000이고, 중복이 없는 수열이 입력으로 주어지면, 경우의 수가 100,000 * (100,000 + 1) / 2이 되므로, long long형을 사용해야합니다. 

 

아래는 전체 코드입니다. 

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

int seq[100010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n; 
    for(int i = 0; i < n; i++) cin >> seq[i];

    int st = 0, en = 0; // st는 중복이 없는 구간의 시작점, en는 끝점 
    long long ans = 0; // 경우의 수 
    
    map<int, int> m;    // st ~ en까지의 수열에 포함된 수가 등장하는 횟수를 저장
    m[seq[st]] = 1;

    while(true){
        while(en < n - 1 && m[seq[en + 1]] == 0){   // seq[en + 1]가 기존 수열에 포함되지 않은 경우
            en++; m[seq[en]]++; // en의 길이를 늘려주고, seq[en]을 수열에 포함 시킴
        }
        if(st >= n || en >= n) break;
    
        ans += en - st + 1; // 경우의 수 증가
        m[seq[st]]--; st++; // seq[st]를 수열에서 제외시키고, st를 이동 시킴
    }
    cout << ans << "\n";
}