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

문제 링크: www.acmicpc.net/problem/13144

13144번: List of Unique Numbers

1. 주의할 점

- 두 포인터로 접근한다

- 아래 TC와 같은 케이스에 대해 정확히 처리한다

TC #1

5
3 4 1 2 4

 

2. 구현

- 입력받는 수들을 Arr[] 배열에 저장한다

- 두 포인터 L,R을 이용하여 L~R까지에 대한 처리를 진행한다

- R이 Num과 같을 때까지 진행한다

- Arr[]값이 나타난 수를 Check[] 배열에 저장하며, 만약 Check[]의 값이 True면 중복된 경우가 있으므로, While문을 통해 Check[]값이 False일때까지 수행한다. If문으로 1번만 진행할 경우, 위의 TC에서 오답을 도출

- While문 안에는 [L,R)까지의 경우의 수인 R-L만큼 Result에 더하고, 왼쪽 포인터에 해당 하는 Check[]값을 False로 바꾸고, 포인터를 오른쪽으로 한칸 옮긴다

- While문이 끝나거나 해당하지 않을 경우, Check[val]=True와 R++를 수행한다

- L~R까지 모든 수들이 겹치지 않을 경우, 시그마 L~R의 공식을 적용하여 Result에 더한다

#include <iostream>
using namespace std;
int arr[100001];
bool check[100001]={false,};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num;
    long long result=0;
    cin>>num;
    for(int i=0;i<num;i++)
        cin>>arr[i];
    int l=0,r=0;
    while(r<num){
        int val = arr[r];
        while(check[val]){
            result+=(r-l);
            check[arr[l++]]=false;
        }
        check[val]=true;
        r++;
    }
    result+=(long long)(r-l)*(r-l+1)/2;
    cout<<result;
    return 0;
}