[Two Pointers] Boj13144: List of Unique Numbers

[Two Pointers] Boj13144: List of Unique Numbers

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

문제

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

입력

• 첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)
• 두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

출력

• 조건을 만족하는 경우의 수를 출력한다.

입출력 예제

코드 | 파이썬

import sys
si = sys.stdin.readline
N = int(si())
N_list = list(map(int,si().split()))
count = [0] * 100001

R = -1
ans = 0
sum = 0
for L in range(N):
    while R+1 < N and count[N_list[R+1]] == 0:
        R += 1
        count[N_list[R]] += 1
        sum += 1
    ans += sum
    sum -= 1
    count[N_list[L]] -= 1

print(ans)

코드 스크린샷 및 결과