[백준13144/골드4] List of Unique Numbers - Python

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

 

부분수열을 만들떄, 부분 수열의 끝 점을 정한 후 그 점 까지 중복된 수가 안나오는 제일 긴 시작점을 구했다. (for end in range(N))

그리고 그 부분수열에서 시작점을 변경하며 나올 수 있는 부분수열의 수를 더해줬다. (end - start + 1)

 

# 성공 코드

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

select = set() # 선택된 수 (슬라이딩 윈도우 안의 수)
start = 0 # 시작점
result = 0

for end in range(N): # 끝점 0번 인덱스부터 끝까지 순회
	
    # 숫자가 중복되면 시작점 제거 후 다음 시작점 탐색
    while numbers[end] in select:
        select.remove(numbers[start])
        start += 1
	
    # 끝점 추가
    select.add(numbers[end])
    
    # 현재 수열에서 경우의 수 계산
    result += (end - start + 1)

print(result)

 

 

윈도우를 옮기면서 현재 끝점에 대한 가장 긴 수열을 찾아서 (시작점 찾기) 경우의 수를 계산해야겠다는 생각은 금방 했지만

끝점과 시작점을 검사하고 중복 제거하는 과정을 푸는데 좀 오래걸렸다.