[백준] 13144번: List of Unique Numbers

문제

백준 - 13144번: List of Unique Numbers

분석

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

N이 최대 100,000 아므로 완전탐색은 불가능하다.
따라서 투포인터를 이용했다.
i, j 포인터를 두고, 딕셔너리로 연속된 수열에서 중복된 것이 있는지 체크하면서
i부터 j까지는 중복된 것이 없게 했다.
경우의 수를 구할 때는 새로 연속된 수열에 추가된 개수를 cnt로 센다.
새로 추가된 수들로 이룰 수 있는 경우의 수는 cnt!로 cnt * (cnt + 1) // 2 가 된다.
새로 추가되기 전에 기존에 연속된 수열의 길이(len(dic))와 새로 추가된 수들의 곱도 경우의 수가 추가된다.
j가 전진을 멈췄을 때 i가 전진해야 한다. 그 전에 딕셔너리에서 arr[i]값을 제거해줘야한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
j = 0
ans = 0
dic = {}
for i in range(n):
    cnt = 0
    pre = len(dic)
    while j < n and arr[j] not in dic:
        dic[arr[j]] = 1
        j += 1
        cnt += 1
    ans += cnt*(cnt+1)//2
    ans += pre*cnt
    del dic[arr[i]]
print(ans)

끝으로..

경우의 수를 세는 방법에서 오래걸렸다.
수학적인 연습이 조금 더 필요한 것 같다.