13144 - List of Unique Number

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

13144번: List of Unique Numbers

생각해보기

1. 같은 수가 여러 번 등장하면 범위가 줄어든다.
2. 투 포인터를 사용하여 우측 값을 하나씩 증가시키며 확인한다.
3. 왼쪽 포인터의 위치는 한칸씩 옮기며 확인하는 것보다는 우측 포인터의 숫자가 나왔던 위치보다 한칸 우측으로 옮기는게 효율적이다.
4. 같은 수가 등장한 위치를 기록해두자.

코드

#include<iostream>

using namespace std;

int N;
int arr[100001];
int chk[100001];
long long ans=0;

void input(){
    cin>>N;
    for(int i=0;i<N;++i)
        cin>>arr[i];
}

void calc(){
    fill(&chk[0], &chk[100001], -1);
    int l=0,r=1;
    ans = 1;

    chk[arr[0]] = 0;
    while(r<N){
        int num = arr[r];
        if(chk[num] >= l){
            l = chk[num]+1;
        }

        ans += r-l+1;
        chk[num] = r;
        ++r;
    }
}

void solution(){
    calc();
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}