[2164] 카드2

 

백준 Silver IV | 2164 | Python | 문제 링크

문제 설명

N장의 카드가 1부터 N까지 순서대로 쌓여 있다. 맨 위 카드를 버리고, 그 다음 맨 위 카드를 맨 아래로 옮기는 동작을 카드가 1장 남을 때까지 반복한다. 마지막에 남은 카드 번호를 출력하면 된다.

입력

첫째 줄에 N (1 ≤ N ≤ 500,000)이 주어진다.

출력

마지막에 남은 카드의 번호를 출력한다.

입출력 예

입력	출력
6	4

 

나의 풀이

풀이 1 - 무한루프가 걸린 첫 제출

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

q = deque()
num = int(input())
for i in range(1, num+1):
    q.append(i)

while q:
    if len(q) == 1:
        print(q[0])       # break가 없다
    else:
        q.popleft()
        q.append(q.popleft())

문제 자체는 어렵지 않았다. deque로 카드 덱을 만들고, popleft()로 버리고, 다시 popleft()해서 append()로 맨 아래에 넣으면 된다. 논리는 맞았다.

제출하고 시간 초과가 떴다. 처음엔 알고리즘 복잡도 문제인가 싶었는데, 코드를 다시 보니 그게 아니었다.

버그 1 — break가 없다

if len(q) == 1:
    print(q[0])

len(q) == 1일 때 출력은 하는데 루프를 빠져나오지 않는다. while q:는 큐가 비어있어야 종료되는데, 카드 1장이 남아있는 채로 계속 돈다. print만 무한히 반복되는 것이다.

출력이 쌓이다 보니 시간 초과로 잡혔다. 무한루프인데 시간 초과로 나오니까 처음에는 영문을 몰랐다. break 한 줄이 빠진 것 때문에 이렇게 됐다는 게, 고치고 나서도 좀 허무했다.

풀이 2 - 최종 제출 코드

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

q = deque()
num = int(input())
for i in range(1, num+1):
    q.append(i)

while q:
    if len(q) == 1:
        print(q[0])
        break           # break 추가
    else:
        q.popleft()
        q.append(q.popleft())

break를 붙이니 바로 통과했다. 코드는 맞는데 루프 종료 조건을 명시적으로 설계하지 않은 게 문제였다.

풀이 3 - 루프 조건 개선

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

q = deque(range(1, int(input()) + 1))

while len(q) > 1:
    q.popleft()
    q.append(q.popleft())

print(q[0])

while len(q) > 1:로 조건을 바꾸면 카드가 1장 남는 순간 자연스럽게 루프가 끝난다. if/else와 break가 둘 다 필요 없어진다. 초기화도 deque(range(1, n+1))로 한 줄로 줄었다.

while q:를 쓰면 큐가 빌 때까지 돌기 때문에 탈출 시점을 코드 안에서 따로 처리해야 한다. while len(q) > 1:은 종료 조건을 루프 헤더에서 바로 표현하기 때문에 break가 끼어들 여지가 없다.

break 한 줄이 빠져서 무한루프가 된 이번 실수도, 애초에 루프 조건을 이렇게 썼다면 일어나지 않았을 것이다.