[BOJ] Q13144 List of Unique Numbers

[BOJ] Q13144 List of Unique Numbers

Question

Language: Python

Difficulty: Gold 4

해당 문제는 Two pointer을 활용하여 가질 수 있는 순서쌍의 갯수를 구하는 유형의 문제이다. 숫자가 삽입 될때 늘어나는 순서쌍의 갯수를 파악하는 것이 중요하다.

아래의 원리를 통해 순서쌍의 갯수를 구하는 과정을 단순화 시킬 수 있다.

만약 새로운 숫자가 탐색 된 경우라면, 위의 로직을 활용하여 추가되는 순서쌍의 갯수를 구하고, 만일 다음에 오는 숫자가 이미 포함된 숫자인 경우, 해당 숫자가 안 나올때 까지 start 값을 늘리는 작업을 수행한다.

Solution

def solution():
    start,end=0,0
    checked=[False]*100001
    count=0

    while end < n:
        #다음에 탐색된 숫자가 이전에 탐색되지 않은 숫자인 경우
        if not checked[numbers[end]]:
            checked[numbers[end]]=True
            end+=1
            count+=(end-start)
        #이미 이전에 처리한 적 있는 숫자인 경우
        else:
            while checked[numbers[end]]:
                checked[numbers[start]]=False
                start+=1
    print(count)


if __name__ == "__main__":
    n=int(input())
    numbers=list(map(int,input().split()))
    solution()