[백준/Python] 13144 List of Unique Numbers

📌문제 탐색하기

• 길이가 N인 수열이 주어짐
• 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수 구하기

입력

• 수열의 길이 N (1 ≤ N ≤ 100,000)
• 수열을 나타내는 N개의 정수 (1 ≤ 수열에 나타나는 수 ≤ 100,000)

출력

• 조건을 만족하는 경우의 수

풀이 방법 생각해보기

연속한 1개 이상의 수를 뽑아야 하므로, 투 포인터를 사용해서 뽑을 수들의 첫번 째 위치와 마지막 위치를 가리키도록 한다. 첫 번째 위치를 설정하고, 마지막 위치를 가리키는 포인터를 한칸 씩 옮겨서 중복된 수가 있는지 없는지 판단하고, 중복된 수가 있다면 다시 첫번째 위치를 한 칸 옮겨 경우의 수를 세면 모든 경우의 수를 구할 수 있다.

이때, 첫번째 위치가 1이고, 마지막 위치를 1부터 5까지 탐색했을 때 경우의 수가 5라면, 첫번째 위치가 2고, 마지막 위치를 2부터 5까지 탐색했을 때 경우의 수는 4가 된다. 이를 활용하여 탐색 시간을 줄일 수 있다.

 

📌코드 설계하기

1. 수열의 길이 N을 입력받는다.
2. numbers 리스트를 생성해 수열을 나타내는 정수들을 입력받아 저장한다.
3. left를 0, right를 0으로 설정한다.
4. 경우의 수를 저장할 변수 counts를 생성하고 0으로 초기화한다.
5. 현재 설정된 left를 기준으로 가능한 경우의 수를 저장할 cur_count를 생성하고 1로 초기화한다.
6. 현재 조사한 범위에서 특정 숫자의 등장 횟수를 기록할 디폴트딕트 count_dict를 생성하고, count_dict[numbers[right]]를 1로 초기화한다.
7. left가 N보다 작을 때까지 아래 과정을 반복한다.
   
   1. right+1 >= N (수열 범위 벗어남)이거나, counts_dict[number[right+1]] (중복 숫자 등장)이라면 counts에 cur_count를 더하고, cur_count에서 1을 빼준다. 그리고 count_dict[numbers[left]]에서 1을 빼고 left에 1을 더한다.
   2. 1의 조건에 걸리지 않는다면, right에 1을 더하고 count_dict[numbers[right]]와 cur_count에 1을 더한다.
8. counts를 출력한다.

 

📌정답 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

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

left = right = counts = 0
cur_count = 1
count_dict = defaultdict(int)
count_dict[numbers[right]] = 1

while left < N:
    if right+1 >= N or count_dict[numbers[right+1]]:
        counts += cur_count
        cur_count -= 1
        count_dict[numbers[left]] -= 1
        left += 1
    else:
        right += 1
        count_dict[numbers[right]] += 1
        cur_count += 1
    
print(counts)