[BOJ / C++] 13144 List Of Unique Numbers

문제 링크

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

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

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

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

예제 입력 1
5
1 2 3 4 5
예제 출력 1
15

예제 입력 2
5
1 2 3 1 2
예제 출력 2
12

예제 입력 3
5
1 1 1 1 1
예제 출력 3
5

문제 정리

세번째 예제를 살펴보자. 배열에 1 2 3 1 2가 있다. 우리는 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구해야 한다. 다 나열해보면

• 1 12 123
• 2 23 231
• 3 31 312
• 1 12
• 2

각각 중복된 수가 나오기 전까지의 경우를 구한 것을 볼 수 있다. 이 경우의 수는 각 시작점과 중복된 수가 나오는 위치 사이의 거리 와도 같다.

이 문제는 투 포인터로 풀 수 있다. A배열에 수열이 있다고 하자.
투 포인터 알고리즘

1. st와 en으로 배열의 시작을 가르킨다.
2. A[en]을 방문 처리하고 en을 증가시킨다. A[en]이 방문 처리가 되어있을 때 까지 반복한다.
3. 경우의 수에 st와 en 사이의 거리를 추가한다.
4. 방문 처리 되어있는 A[st]의 방문을 해제하고 st의 값을 1 증가시킨다.
5. st가 배열의 범위를 벗어날 때 까지 2,3,4번을 반복한다.

내가 설명했는데도 너무 어렵게 설명한 것 같다.A[en]을 방문처리한다A[en]을 방문처리가 되어있던 1까지 증가시키고 st와 en의 거리를 경우의 수에 추가한다.A[st]의 방문을 해제하고 st를 1 증가시킨다. 그 뒤 과정의 설명은 생략하겠다. 주의할 점은 en이 배열의 범위를 벗어나게 되면 en의 위치를 배열의 마지막+1로 고정시킨 뒤 en-st를 구한다.

구현 코드

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

int main()
{
    int arr[100009];
    bool vis[100009];
    
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++)
        cin >> arr[i];
    
    int en = 0;
    long result = 0;
    for(int st=0; st<n; st++)
    {
        while(en < n)
        {   
            if(vis[arr[en]])
                break;
            vis[arr[en]]=1;
            en++;
        }
        result += en - st  ;
        
        vis[arr[st]] = false;

    }

    cout << result;
}

너무 설명을 어렵게 한 것 같지만 이해가 됐으면 좋겠다..!