[백준/Python]13144: List of Unique Numbers

문제

https://www.acmicpc.net/problem/13144
백준 문제집 - 0x14강 - 투 포인터

 

알고리즘: 투 포인터

---

풀이

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

 

각기 다른 숫자로 이루어진 연속된 부분 수열의 갯수를 구하는 문제다.
즉, 예제 2처럼 [1, 2, 3, 1, 2]가 주어졌을 경우 가능한 부분 수열은 아래와 같다.

# 1개
[1]. [2], [3], [1], [2]
# 2개
[1, 2], [2, 3], [3, 1], [1, 2]
# 3개
[1, 2, 3], [2, 3, 1], [3, 1, 2]
# 4개, 5개는 불가능
# 답: 12

 

위 예제만 보고 set()으로 관리하려 했으나 아래와 같은 반례가 있었다.

# 출처: https://www.acmicpc.net/board/view/128564

5
1 2 2 2 1

#wrong
9

#answer
7

set을 사용하는 방법은 예제 2와 같이 "중복되는 숫자 == 기존 수열의 가장 왼쪽 숫자" 일 때에만 가능한것이었다.

그런고로 수열에 포함된 각 숫자의 갯수를 정확히 파악하려면 해시(딕셔너리)를 사용해야한다.

1. 현재 추가한 숫자의 갯수를 카운트한다.
2. 만약 1이 아니라면, 1이 될 때까지 left 숫자의 갯수를 감소시키며 left 포인터를 오른쪽으로 한칸씩 이동한다.
3. 나올 수 있는 수열의 갯수를 카운트한다.

나올 수 있는 수열의 갯수는 수열의 길이를 더한 값과 같다.
right를 left부터 right까지 증가시키면서 "right를 포함하는 수열의 갯수"를 더해간다고 생각하면 된다.
예를들어 [1, 2, 3, 4, 5]가 있고 left = 0, right = 2 라고 한다면 수열의 갯수를 세는 과정은 아래와 같다.

# right = 0 / 선택범위: [1]
[1]
=> 1개

# right = 1 / 선택범위: [1, 2]
[2]
[1, 2]
=> 2개

# right = 2 / 선택범위: [1, 2, 3]
[3]
[2, 3]
[1, 2, 3]
=> 3개

답: 6

 

전체 코드

# 메모리: 46492KB / 시간: 136ms
from sys import stdin


input = stdin.readline

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

nums = {}  # 수의 갯수를 체크할 딕셔너리

cnt = 0
left = 0

for right in range(N):
    nums[arr[right]] = nums.get(arr[right], 0) + 1

    # 현재 추가한 수의 갯수가 1이 될 때까지
    while nums[arr[right]] > 1:
        nums[arr[left]] -= 1  # 가장 왼쪽 인덱스의 숫자를 감소시킴
        left += 1

    cnt += right - left + 1  # 나올 수 있는 수열의 갯수 카운트

print(cnt)