[PS] 백준 13144번 List of Unique Numbers

이번에는 백준 13144번 List of Unique Numbers 문제를 풀어보았습니다.

이 문제는 연속 부분 수열 중 같은 숫자가 한 번도 등장하지 않는 경우의 수를 구하는 문제입니다.

처음에는 모든 구간을 확인하는 완전탐색을 생각했지만, 시간복잡도가 O(N^2)가 되어 불가능했습니다.

대신 투포인터를 이용하여 현재 구간에 중복이 없도록 유지하면서 모든 경우를 계산할 수 있었습니다.

---

문제 설명

길이 N인 수열이 주어집니다.

연속한 부분 수열 중

• 같은 숫자가 두 번 이상 등장하지 않는

부분 수열의 개수를 구하는 문제입니다.

---

풀이 아이디어

항상

[st, ed] 구간에는 중복되는 숫자가 없다.

라는 조건을 유지하도록 투포인터를 사용하였습니다.

ed를 한 칸씩 증가시키다가

이미 존재하는 숫자가 나오면

중복이 없어질 때까지 st를 앞으로 이동시킵니다.

이렇게 하면 모든 구간을 한 번씩만 확인하게 됩니다.

---

코드

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

bool visited[100001];
int inp[100001];
long long cnt;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    int st = 0;

    for (int i=0; i<N; i++) {
        cin >> inp[i];
    }

    for (int ed=0; ed<N; ed++) {

        while (visited[inp[ed]]) {
            visited[inp[st]] = false;
            st++;
        }

        visited[inp[ed]] = true;

        cnt += (ed - st + 1);
    }

    cout << cnt;

    return 0;
}

---

풀이 흐름

1. 시작점 st와 끝점 ed를 준비합니다.
2. ed를 한 칸씩 증가시킵니다.
3. 현재 숫자가 이미 구간 안에 존재하면 중복이 없어질 때까지 st를 이동합니다.
4. 현재 숫자를 방문 처리합니다.
5. 현재 끝점에서 만들 수 있는 모든 부분 수열의 개수를 더합니다.
6. 모든 원소를 확인한 뒤 결과를 출력합니다.

---

구현 포인트

1. 현재 구간에는 중복이 없도록 유지

항상

[st, ed]

구간에는 같은 숫자가 존재하지 않도록 유지합니다.

현재 숫자가 이미 존재한다면

while (visited[inp[ed]]) {
    visited[inp[st]] = false;
    st++;
}

를 통해 중복이 사라질 때까지 시작점을 이동시켰습니다.

---

2. 방문 여부 관리

현재 구간에 포함된 숫자는

visited[]

배열로 관리하였습니다.

새로운 숫자를 추가할 때는

visited[inp[ed]] = true;

구간에서 제외될 때는

visited[inp[st]] = false;

로 관리하여 현재 구간의 상태를 유지하였습니다.

---

3. 경우의 수 계산

중복이 없는 구간이

[st, ed]

라면

끝점이 ed인 부분 수열은

[ed]
[ed-1 ~ ed]
...
[st ~ ed]

처럼 총

ed - st + 1

개가 존재합니다.

따라서

cnt += (ed - st + 1);

를 수행하면 현재 끝점을 기준으로 만들 수 있는 모든 경우를 한 번에 더할 수 있습니다.

---

4. 시간복잡도

st와 ed는 모두 최대 N번씩만 이동합니다.

따라서 전체 시간복잡도는

O(N)

으로 문제를 해결할 수 있습니다.