[python] 백준 13144 List of Unique Numbers

https://www.acmicpc.net/problem/13144

13144번: List of Unique Numbers

문제 해결

• 투포인터 (start, end)를 이용해 수열 시작점과 끝점을 잡는다.
• start==end가 될 수 있다. 한개의 수도 경우의 수에 포함되기 때문이다.
• end를 +1씩 해가면서 문장 안에 있는 수와 같은 것이 없으면 계속 나아간다.
• 만약 같은 것이 생기면 start지점을 하나씩 옮겨 가며 같은수를 만날 때 까지 start지점을 이동시킨다.
• 그래서 중복된 수가 없도록 수열을 만들어나가며 경우의 수를 계산한다.

 

CODE

n = int(input())
A = list(map(int, input().split()))
start = 0; end = 0
answer = 0
visited = [False]*100001
while start <= end and end <n:
    if not visited[A[end]]:
        visited[A[end]] = True
        end += 1
        answer += end-start
    else:
        while visited[A[end]]:
            visited[A[start]] = False
            start += 1
print(answer)