[백준 13144] List of Unique Numbers cpp

 

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

13144번: List of Unique Numbers

 

문제

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

입력

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

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

출력

 

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

 

 

 

 풀이

 

전형적인 투 포인터 알고리즘 문제이다.

 

n개의 수열이 담긴 배열을 투 포인터로 탐색 한다.

 

같은 수가 여러 번 들어 있는지 확인 하는 check 배열을 통해

여러 번 들어있지 않으면 오른쪽 (rt) 포인터를 이동시킨다.

 

 

 

만약 같은 수가 여러번 등장할 경우 

전체 경우의 수에서 해당 범위 (n-rt) 를 빼준뒤 

lt (왼쪽 포인터)을 이동한다.

 

왼쪽 포인터를 이동하면서 check 배열을 초기화 시켜줘야 한다.

 

 

이런식으로 rt가 배열 끝에 도달할 때 까지 탐색을 하면

O(n) 의 시간 복잡도로 문제를 해결 할 수 있다.

 

 

※ 연속한 n개 이상의 수를 뽑는 경우의 수 => n(n+1) / 2

 

 

 

코드는 다음과 같다.

#include "bits/stdc++.h"

using namespace std;

int arr[100001];
bool checked[100001];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, ans;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    ans = n * (n + 1) / 2;
    int lt = 0;
    int rt = 1;
    checked[arr[lt]] = true;
    while (rt < n) {
        if (checked[arr[rt]]){
            checked[arr[lt]] = false;
            lt++;
            ans -= n-rt;
        }else {
            checked[arr[rt]] = true;
            rt++;
        }
    }
    cout << ans;
}