[백준 c++] 13144 List of Unique Numbers

문제 설명

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

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

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

풀이

투 포인터를 이용해서 푸는 문제로 간단해보였지만 푸는데 오래 걸렸던 문제다ㅠ

1 2 3 1 2

1. 지금 뽑은 수가 이전까지 뽑은 수들과 중복이 아니면 end 포인터++

2. 중복이면 res+=(end-start), start 포인터++

   res += (end-start): 직전까지는 중복이 없었다는 뜻이므로 맨 앞의 수를 포함한 연속 수를 만든다.
   ex) start = 0, end = 3 일 때 중복이 발생
   => 1, 1 2, 1 2 3 => 3
   start++,

3. end 포인터가 수열 길이 n과 같아지면 반복문 종료
   남은 수들을 가지고 연속수를 만들 수 있는 경우의 수는 (end-start)! 이다.

지금 뽑은 수가 이전까지 뽑은 수와 중복되는 수 인지 판별하는 것도 관건이었다. 2중 for문을 썼다간 시간초과가 나기 때문에 배열을 이용해야한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, s, e, a[100001], cnt[100001];
long long res;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    while (e < n)
    {
        if (!cnt[a[e]])
        {
            cnt[a[e]]++;
            e++;
        }
        else
        {
            res += (e - s);
            cnt[a[s]]--;
            s++;
        }
    }
    for (int i = 1; i <= e - s; i++)
    {
        res += i;
    }
    cout << res << "\n";
}