[BOJ] #13144 List of Unique Numbers (Python)

🌱 문제

13144번: List of Unique Numbers

 

🌱 풀이

0. 입력 받기

n = int(input().rstrip())
num_list = list(map(int, input().split()))

수열의 길이와 수열의 원소 값들을 입력받습니다.

1. 변수 초기화

result = 0
start, end = 0, 0
seq = [False] * 1000001

• 투포인터를 이용해 풀기 위해 num_list의 인덱스를 가리킬 start와 end를 각각 0으로 초기화 해줍니다.
• seq에 수열에 들어갈 수 있는 최댓값인 100000 크기의 배열을 만들고, 숫자가 중복되었는지 체크합니다.

2. 투포인터 알고리즘

while start < n and end < n:
    if not seq[num_list[end]]:      # start부터 end까지 중복 숫자 없으면
        seq[num_list[end]] = True
        end += 1
        result += (end - start)     # end를 포함하여 만들 수 있는 수열의 개수
    else:
        seq[num_list[start]] = False
        start += 1

• start와 end가 모두 마지막 원소를 가리킬 때까지 반복합니다.
• 만약 end가 가리키는 숫자가 아직까지 나오지 않았다면, start부터 end까지 end를 포함하는 수열의 조합의 개수인 end + 1 - start를 result에 더하고, end는 전진시킵니다.
  예를 들어, [1, 2, 3, 1, 2] 수열에서 start가 0이고, end가 2일때, end를 포함하여 만들 수 있는 조합은 [3], [2, 3], [1, 2, 3]으로 3개(end + 1 - start = 2 + 1- 0 = 3) 입니다.
  end를 미리 전진시켜놓으면 result를 계산할 때 +1을 생략할 수 있습니다.
• 만약 end가 가리키는 수가 이미 나왔다면(중복되었다면), start를 전진시킵니다. 그리고 현재의 start는 안나온 값으로 취급해주어야 하므로 seq에서 start가 가리키는 수를 False 처리합니다.

 

🌱 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 13144 List of Unique Numbers

import sys
from collections import defaultdict

num_dict = defaultdict(list)
input = sys.stdin.readline
n = int(input().rstrip())

num_list = list(map(int, input().split()))

result = 0
start, end = 0, 0
seq = [False for _ in range(1000001)]
while start < n and end < n:
    if not seq[num_list[end]]:      # start부터 end까지 중복 숫자 없으면
        seq[num_list[end]] = True
        end += 1
        result += (end - start)     # end를 포함하여 만들 수 있는 수열의 개수
    else:
        seq[num_list[start]] = False
        start += 1

print(result)