코드

시간 초과 (Coner Case 처리 안 함)

n = int(input())

cards = list(range(1, n+1))

cnt = 0
for i in range(n):
    
    #print('cards : ', cards)
    f = cards.pop(0)
    #print(f)
    p = cards.pop(0)
    #print(p)
    cards.append(p)
    cnt += 1
    
    #print(i, ' : ', cards)  
    
    if cnt == n or len(cards) == 1:
        break
        
print(cards[0])

deque 사용

import sys
from collections import deque

n = int(sys.stdin.readline())
cards_qu = deque()

for i in range(n):
    cards_qu.append(i + 1)
    
while len(cards_qu) > 1:
    cards_qu.popleft()
    cards_qu.append(cards_qu.popleft())
    
print(cards_qu.pop())

규칙 이용

n = int(sys.stdin.readline())
c = 2

while True:
    if n == 1 or n == 2:
        print(n)
        break
    
    # c가 2의 제곱수
    c *= 2
    
    # c가 n보다 큰 경우에만 동작
    if c >= n:
        # n보다 작은 2의 제곱수 중 가장 큰 수
        print((n - (c // 2)) * 2)
        break

문제 해설

단순히 List를 이용해보니 시간 초과가 나왔다. 이 문제의 경우 sys.stdin.readline()를 사용하고 Pypy3으로 제출하여도 시간 초과가 나오는 것을 보고 List를 사용하면 안 된다는 것을 깨닫고 고민하다가 deque를 사용해야겠다고 느끼고 문제를 푸니 정답으로 인정됐다.

또한 문제를 푸는 도중 규칙이 있는 것 같은데 그 규칙을 점화식으로 작성하는 것이 잘 되지 않아 구글링을 통해 찾아서 규칙을 이용하여 문제를 풀어보았다.

규칙 참고 블로그

규칙을 파악하기 위해 앞으로 다양한 입력값으로 결과를 도출해보고 위의 블로그 작성자분처럼 정리해서 파악하는 연습을 해야겠다.

댓글남기기

참고