백준 13144 List of Unique Numbers Python

🐸 문제 정보

13144번: List of Unique Numbers

 

🤖 알고리즘

투포인터

 

⏱️ 풀이 시간

60m+

 

📝 풀이

생각보다 어려운 문제였다ㅠㅠ

처음에는 투포인터를 이용해서 앞부터 순회하며, start가 1커진다면 이전 start에서 구한 수열 - 1 개로 초기화되는 방식(dp + 투포인터)으로 구현하였으나 start와 end가 같아지는 시점에서 예외처리가 너무 많아 포기하게 됐다.

검색을 통해 end에서 start를 빼주면서 개수를 더해주는 아이디어를 얻었는데, 풀고나서 보니 대부분의 사람들이 dictionary를 사용하는 것을 알 수 있었다.

나는 set을 이용하였는데, set이나 dictionary나 검색에서는 O(n)이기 떄문에 상관없다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))

s, e = 0, 0
dup = set()
res = 0
while (s != n) and (e != n):
    if nums[e] not in dup:
        dup.add(nums[e])
        e += 1
        res += e - s
    else:
        while nums[e] in dup:
            dup.remove(nums[s])
            s += 1

print(res)