[백준] 13144번 List of Unique Numbers

문제: 13144번: List of Unique Numbers

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> nums(n);
    vector<int> used(100001); // 수가 이미 사용중인 수인지 체크.. 0 번 인덱스 안 써
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int st = 0;
    int en = 0;
    long long ans = 0;
    while (en < n) {
        while (used[nums[en]] == 1) {
            // 중복이 발생하면 st 를 이동하여 해결
            used[nums[st]] = 0;
            st++;
        }
        used[nums[en]] = 1;
        ans += (en - st + 1); // 현재 en 을 포함한 부분 수열 개수를 더함
        en++;
    }
    cout << ans;

    return 0;
}

 

아나 처음에 너무 어렵게 생각해서 틀렸다.

 

그냥 단순하게 현재 수열에 추가하려고 하는 부분이 이미 수열에 존재한다면 해당 이전에 나왔던 수를 지울때까지 st 값을 증가시켜준다.

 

현재 수열에 추가하려고 하는 부분이 수열에 존재하지 않는다면 그냥 used[nums[en]] = 1 로 사용 표시 해주고 ans 에 현재 연속 부분 수열의 길이를 더해주고 en 의 크기를 +1 해주면 된다.

 

그리고 마지막에 ans 를 출력해주면 끝!