[백준] 2164번: 카드2

문제

약간 요세푸스가 떠오르는 문제!
처음에는 요세푸스 문제를 보고서는 공식을 만들어야 할까하는 생각이 들었지만,
사실 큐 같은 경우 범위지정만 잘하고, 문제에서 말하는 것을 그대로 코드로 구현하기만 하면 크게 어렵지 않다.

요세푸스?

풀이

시간 초과

num = int(input())
queue = [i for i in range(1, num+1)]

while len(queue)>1:
    queue.pop(0)
    
    queue = queue[1:]+[queue[0]]
print(*queue)

list 쓰는 문제인데 시간 초과가 나오면 바로 deque으로 바꾼다.
그럼 높은 확률로 통과가 된다.

53380KB 228ms

card = deque()
num = int(input())
queue = [i for i in range(1, num+1)]
card.extend(queue)

for _ in range(num-1):
    card.popleft()
    temp = card.popleft()
    card.append(temp)

print(*card)

우수코드

list를 썼는데도, 시간초과가 안 나는 코드가 있어서 들고왔는데,
간혹 답에 대한 규칙을 바로 찾을 수 있다면
굳이 문제에서 말하는대로 액션을 취하지 않고
바로 답을 도출하는 식으로 짜면 될 것 같다.

n = int(input())
s = 1
while True:
    if s * 2 > n:
        break
    else:
        s *= 2
if n == s:
    print(s)
else:
    print(n - (s - (n - s)))