백준 13114: List of Unique Numbers(파이썬)

💡 문제 요약

1부터 N까지의 수열이 주어진다.
서로 다른 값으로 이루어진 연속 부분 수열(subarray)의 개수를 구하는 문제이다.

• 수열 A의 i번째 요소부터 j번째 요소까지, 모든 수가 서로 다르면 해당 구간을 하나로 센다.
• X ≤ Y를 만족하는 모든 (X, Y) 쌍에 대해 구간을 탐색하여, 중복 없는 경우만 세야 한다.

---

🧠 문제 배경

이 문제는 투 포인터(two pointers) 또는 슬라이딩 윈도우(sliding window) 알고리즘의 대표적인 유형이다.

• 연속된 구간 내에서 중복이 없는 최대 범위를 빠르게 탐색해야 한다.
• 단순 이중 반복문을 쓰면 O(N²)으로 시간 초과가 발생하므로,
• 포인터를 이동시키면서 중복을 관리하여 O(N)으로 최적화해야 한다.

---

🔍 알고리즘 설계

🔴 전 코드 (비효율적)

import sys
input = sys.stdin.readline

N = int(input())
number_lst = list(map(int, input().split()))
count = 0
new_lst = []
flag = 0

for i in range(len(number_lst)):
    if number_lst[i] in new_lst:
        if flag == 0:
            for j in range(len(new_lst) + 1):
                count += j
                flag = 1
        else:
            for j in range(len(new_lst)):
                count += j
    else:
        new_lst.append(number_lst[i])

if flag == 0:
    for j in range(len(new_lst) + 1):
        count += j
else:
    for j in range(len(new_lst)):
        count += j

print(count)

---

🟢 후 코드 (최적화된 방식)

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

last_seen = {}
ans = 0
l = 0

for r in range(N):
    x = A[r]
    if x in last_seen and last_seen[x] >= l:
        l = last_seen[x] + 1

    last_seen[x] = r
    ans += (r - l + 1)

print(ans)

---

✅ 시간 복잡도 분석

단계	연산량	복잡도
입력 처리	N개 읽기	O(N)
last_seen 관리	숫자마다 1회 조회 및 갱신	O(N)
포인터 이동 및 답 계산	각 요소 1회 처리	O(N)

최종 시간 복잡도: O(N)

---

📌 정리

• 처음에는 리스트로 중복 체크를 하여 시간 복잡도가 높았다.
• 이후 딕셔너리로 마지막 등장 위치를 기록하는 방식으로 최적화하였다.
• 슬라이딩 윈도우를 통해 구간을 관리하면 서로 다른 원소로 구성된 구간을 빠르게 탐색할 수 있다.
• 이 기법은 문자열, 배열, 해시를 다루는 다양한 문제에도 응용할 수 있다.