[백준 13144] List of Unique Numbers (Python)
13144번: List of Unique Numbers
길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.
www.acmicpc.net
문제풀이
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)
결과
문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!