문제
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.
내 풀이
from collections import deque
n = int(input())
q = deque(x+1 for x in range(n))
while len(q) > 1:
q.popleft()
q.append(q.popleft())
print(q[0])코멘트
처음에는 단순히 1에서 N까지 늘어선 카드들을 맨 위 카드 버리기 → 그 다음 카드 맨 뒤로 보내기만 반복하기 때문에 규칙이 있을거라 생각하고 규칙을 찾았었는데, 잘못된 규칙을 찾아서 오답을 받았다. 그 후 다른 풀이를 찾아보니 queue를 연습하는 문제라고 하여 queue를 이용하여 풀어서 정답을 받았다.
내가 잘못된 규칙을 찾아서 오답을 받기는 했지만 규칙이 있기는 있어서 찾아보니 다음과 같았다.
- N이 2의 거듭제곱일 때 : 마지막에 남는 수 = N
- 그 외 : 마지막에 남는 수 = (N - L) 2
여기서 L = N 이하의 가장 큰 2의 거듭제곱
따라서 이를 코드화하면
n = int(input())
power = 1
while power*2 <= n:
power *= 2
if n == power:
print(n)
else:
print((n-power)*2)이렇게 풀면 의 시간 복잡도로 문제를 해결할 수 있다고 한다.
실제로 백준 채점 기록을 보니 위의 queue를 이용한 풀이가 메모리 = 51848 KB, 시간 = 188 ms이 걸렸는데 규칙을 이용한 풀이는 메모리 = 32412 KB, 시간 = 40 ms로 메모리와 시간이 적게 든 것을 확인할 수 있었다.
References
https://www.acmicpc.net/problem/2164
https://velog.io/@error_io/%EB%B0%B1%EC%A4%80-2164-%EC%B9%B4%EB%93%9C2-Python
