[ 13144 ] [ Two-Pointer ] List of Unique Numbers

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

13144번: List of Unique Numbers

---

풀이 과정

---

1. 수열의 왼쪽에서부터 순차적으로 진행한다.

   • 현재의 숫자가 존재하지 않는다면 큐에 넣어준다.
   • 현재의 숫자가 큐에 존재한다면, 현재 숫자가 나올때 까지 큐에서 빼내준 다음 현재 숫자를 넣는다.

2. 현재 큐의 길이를 따로 저장해 둔다.

   • 이유는 현재 숫자가 5고, 큐에 [2, 3, 5]가 들어있다면 경우의 수는 [2, 3, 5], [3, 5], [5] 3가지 즉, 큐의 길이만큼의 경우의 수가 나올 수 있다.

3. 저장해둔 큐의 길이의 합계를 출력해주면 된다

   • 전체 경우의 수를 구해야 하므로

---

소스 코드

---

import sys
from collections import deque

input = lambda : sys.stdin.readline().rstrip()

n = int(input())
sequence = list(map(int, input().split()))

dp = [0] * len(sequence)
queue = deque()
current = set()
for i in range(len(sequence)):
    if sequence[i] in current:
        while queue:
            pos, value = queue.popleft()
            current.remove(value)
            if value == sequence[i]:
                break
    queue.append([i, sequence[i]])
    current.add(sequence[i])

    dp[i] = len(current)

print(sum(dp))