[백준/Python] 2164 카드2

문제: https://www.acmicpc.net/problem/2164

 

 

사용 알고리즘: 덱

 

 

입력

• 첫째 줄에 정수 N (1 <= N <= 500,000)

 

N 장의 카드가 순서대로 쌓여있을 때, 카드가 한 장만 남을 때까지 아래의 동작을 반복

1. 맨 위에 있는 카드 제거

2. 제거되고 맨 위로 나온 카드를 맨 아래에 넣음

 

-> 앞뒤로 추가/제거가 가능하니 덱을 사용해 구현해야겠다

 

 

이 문제는 정말 문제대로만 구현하면 되는 간단한 문제였다. 

 

대신 for 문을 N 회가 아닌 (N-1) 회 돌아야 한다. (덱에 카드가 1장 남았을 때 종료해야 하므로)

d = deque(i for i in range(1,N+1)) # 덱에 1~N 번의 카드를 미리 넣음

for i in range(1, N):
    d.popleft() # 맨 위 카드 제거
    d.append(d.popleft()) # 제거되고 위로 나온 카드를 제거해서 맨 아래에 넣음

 

 

출력은 덱에 한 장 남은 카드를 출력해주면 된다. 

print(d[0])

 

 

전체 코드

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

# 입력
N = int(input())

d = deque(i for i in range(1,N+1)) # 덱에 1~N 번의 카드를 미리 넣음

for i in range(1, N):
    d.popleft() # 맨 위 카드 제거
    d.append(d.popleft()) # 제거되고 위로 나온 카드를 제거해서 맨 아래에 넣음

# 출력
print(d[0])

 

 

 

시간 복잡도

 

- 입력

N = int(input()) # O(1)

 

- 나머지 부분

 

popleft / append : O(1)

d = deque(i for i in range(1,N+1)) # O(N)

for i in range(1, N): # O(N-1)= O(N)
    d.popleft()
    d.append(d.popleft())

print(d[0]) # O(1)

# 총 시간 복잡도는 O(N) + O(N) + O(1) = O(N)

 

 

그래서 총 시간 복잡도는 O(1) + O(N) = O(N) 이다.

- 입력: O(1)

- 나머지 부분: O(N)