[백준 2164 카드2-python] 큐를 사용한 풀이와 큐를 사용하지 않는 ad-hoc 풀이

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

2164번: 카드2

 

큐를 활용한 풀이

x : 삭제 연산

b : 뒤로 보내기 연산

이라고 했을 때 N=5인 경우는 아래와 같이 진행된다.

 

Iter 1

12345

xbooo (1을 삭제 2를 뒤로 보내기)

 

Iter 2

3452

xboo

 

Iter 3

524

xbo

 

Iter 4

42

xb

 

남은 2가 정답!

 

데이터의 흐름이 앞 - 12345 - 뒤 라고 생각했을 때

앞에서 뒤로만 이동한다. queue를 사용해야함

queue를 사용하고자 할 때 파이썬에서는 collections 모듈의 deque 클래스를 import해서 사용한다.

 

from collections import deque
n = int(input())

queue = deque([i for i in range(1,n+1)])
while len(queue) >1:
    queue.popleft()
		# 파이썬의 pop() 함수 계열은 큐나 스택에서 삭제만 하는 것이 아니라, 그 값을 반환한다.
    queue.append(queue.popleft())

print(queue.pop())

 

 

큐를 사용하지 않는 ad-hoc 풀이(억지)

매 Iteration 마다 큐의 앞의 2개의 데이터가 변화한다는 것에서 규칙이 있지 않을까 파악해본 풀이

 

 

n=5일 때 1회의 삭제와 뒤로보내기 연산을 한 결과에서, n=4일 때 답이 4였다는 것을 활용하여

n=5일 때 1회의 연산 이후 결과 배열인 [3, 4, 5, 2] 에서 4번째(index : 3)의 숫자가 답이 된다는 것을 이전의 정답으로 알아낼 수 있다.

즉, n=k 의 정답은 , n=k-1의 정답에 영향을 받는다.

 

자세히 적어보자면 $f(n)\  =\  f(n)_1의\  f(n-1)번째\  수\  (f(n)_1 = \ n개의 \ 카드로\  1회의\  연산을\  진행한\  결과)$ 라는 규칙이 있는데, 이는 n이 6이상일 때에도 성립한다.

 

수학적으로 증명은 안되지만, 아주 나름의 뒷받침할 근거를 발견했는데,

n≥2 인 n에 대해서 모든 정답은 짝수만 나올 수 있다는 규칙을 찾았다.

(1 삭제, 2 뒤로보내기)

(3 삭제, 4 뒤로보내기)

….

이렇게 진행하여 초기 상태의 큐에 존재하는 홀수들이 가장 먼저 삭제되기 때문이다.

예를 들어 12345678의 초기상태였다면, 1,3,5,7번째 숫자는 삭제되고 2,4,6,8번째 숫자는 뒤로밀려나며 4번의 반복을 진행한 후엔 순서가어쨌든 2,4,6,8의 짝수들만 남아있게 된다. 

 

 

 

n = int(input())
if n<3:
    print(n)
else:
    answer = 2
    for i in range(3,n+1):
        answer = 2 if answer + 2 > i else answer + 2
				# 아래의 조건문 분기를 하나로 합친것과 같음
				#if answer + 2 > i:
				#	answer = 2
				#else:
				#	answer +=2
    print(answer)

이렇게 해결하면

 

 

 

위 : 큐를 사용하지 않은 풀이

아래 : 큐를 사용한 풀이

위와 아래의 풀이 모두 시간복잡도는 O(n) 이지만,

메모리와 시간 측면에서 많은 절약을 할 수 있다.