[백준 13144] List of Unique Numbers (Python)

www.acmicpc.net/problem/13144

13144번: List of Unique Numbers

 

문제풀이

N, arr : 입력값

check : 특정 원소 방문 여부 체크

start, end : 투 포인터

dp : i번째 인덱스에서 가능한 경우의 수

q : 현재 수열

tmp : 현재 수열에서 새롭게 탐색한 원소의 개수

 

투 포인터(Two-Pointer)와 DP를 이용해 해결할 수 있었다. 조금 더 효율적인 방법이 있지 않을까 라고 생각이 든다.

 

DP에 대해서 아래의 테스트케이스를 예로 들면

5

1 2 3 3 2

start가 0일때(arr[0] = 1) 가능한 경우의 수는 3 이다. < (1), (1,2), (1,2,3) >

start가 1일때(arr[1] = 2) 가능한 경우의 수는 2 이다. < (2), (2, 3) >

start가 2일때(arr[2] = 3) 가능한 경우의 수는 1 이다. < (3) >

start가 3일때(arr[3] = 3) 가능한 경우의 수는 2 이다. < (3), (3, 2) >

start가 4일때(arr[4] = 2) 가능한 경우의 수는 1 이다. < (2) >

즉, 새롭게 탐색할 원소가 이미 수열에 들어있을 경우, start 에서 가능한 경우의 수는 start - 1 에서 가능한 경우의 수 에서 1을 뺀 경우의 수다. 전체 수열의 끝까지 도달했을 경우도 마찬가지이다.

 

새롭게 탐색한 원소가 수열에 없을 경우 해당 원소를 수열에 넣고 tmp를 1씩 증가시켜보면서 전체 수열의 끝에 도달하거나 특정 원소가 이미 수열에 들어있을 때 까지 반복해서 확인해보면 된다. 

 

코드 및 주석을 확인하면 더 쉽게 이해할 수 있다.

 

1. 투 포인터를 이용해 오른쪽으로  (1) arr의 끝에 도달하거나, (2) 현재 수열에 해당 숫자가 있을 때까지 하나의 원소씩 탐색한다.

- 해당 숫자가 없을 경우 현재 수열에 삽입하면서 새롭게 탐색한 원소 개수(tmp) 증가, 해당 원소 방문 여부(check) 변경

 

2. 새롭게 탐색한 원소가 없을 경우(flag == False) start 인덱스에서 가능한 경우의 수는 start - 1 인덱스에서 가능한 경우의 수의 - 1  

 

3. 새롭게 탐색한 원소가 있을 경우(flag == True) start 가 0 일때를 제외하고 start 인덱스에서 가능한 경우의 수는 start - 1 인덱스에서 가능한 경우의 수의 - 1 + tmp(새롭게 탐색한 원소의 개수) 이다.

 

4. 수열의 첫 원소를 빼고 1, 2, 3 과정을 반복한다.

 

코드

import sys
from collections import deque

if __name__ == '__main__':
    N = int(input())
    arr = list(map(int, sys.stdin.readline().split()))
    check = [False] * 100001 # 특정 원소 방문 여부 체크
    end, ans = 0, 0
    dp = [0] * N # 경우의 수 메모라이제이션
    q = deque() # 현재 수열

    # 투 포인터 활용
    for start in range(N):
        tmp = 0 # 현재 수열에서 새롭게 탐색한 원소의 개수
        flag = False
        # 오른쪽 방향으로 하나씩 탐색
        while end < N and not check[arr[end]]:
            flag = True
            check[arr[end]] = True # arr[end] 원소 방문
            q.append(arr[end]) # 현재 수열에 삽입
            end += 1 # 우측 인덱스 증가
            tmp += 1 # 새롭게 탐색한 원소 개수 증가
        # 우측 인덱스의 원소가 현재 수열에 있으면
        if not flag: dp[start] += (dp[start - 1] - 1) # start 일때의 경우의 수는 start - 1 일 때의 경우의 수 - 1
        else: # 우측 인덱스의 원소가 현재 수열에 없으면
            # start 일때의 경우의 수는 start - 1 일 때의 경우의 수 - 1 에다가 새롭게 탐색한 원소 개수(tmp) 더하기
            if start > 0: dp[start] += (dp[start - 1] - 1 + tmp)
            else: dp[start] += tmp # start 가 0일 경우에만 tmp 더해주기
        # 수열에서 좌측 인덱스 원소 빼주기
        x = q[0]
        check[x] = False
        q.popleft()
    for i in range(N):
        ans += dp[i]
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!