문제 링크 : https://www.acmicpc.net/problem/2164
큐를 활용한 풀이
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) 이지만,
메모리와 시간 측면에서 많은 절약을 할 수 있다.