백준 2164번 - 카드2

첫 번째 시도

cards = [i+1 for i in range(int(input()))]
while len(cards) != 1:
  cards.pop(0)
  cards.append(cards.pop(0))
print(*cards)

시간초과 error…

두 번째 시도

cards = [i+1 for i in range(int(input()))]
while len(cards) != 1:
  if len(cards)%2==0:
    cards = cards[1::2]
  else:
    cards =  [cards[-1]] + cards[1::2]
print(*cards)

홀짝성에 따른 규칙 아이디어를 적용해서 시간초과 에러를 해결하고자 했다.

홀수순서는 제거되고, 짝수순서는 맨 뒤에 옮겨지기에 순서가 그대로이다.

다만, 전체 카드 갯수가 홀수인 경우에는 마지막 카드를 고려해주어야 한다.

고수의 풀이

n,m=int(input()),1
while m<n:m*=2
print(n*2-m)

출처

다른 풀이

deque을 활용해보자! 첫 번째 풀이와 형태가 거의 유사하다. collections라이브러리에서 deque을 불러오면 된다.

from collections import deque

cards = deque([i+1 for i in range(int(input()))])
while len(cards) != 1:
  cards.popleft()
  cards.append(cards.popleft())
print(*cards)

CODE REVIEW

나의 경우 제거해나가는 과정을 구현해서 컴퓨터가 답을 구해나가도록 했지만, 고수의 경우 (n, ans) 순서쌍 사이의 관계식을 찾아서 해결했다.
메모리나 시간 면에서는 규칙을 찾아서 해결하는 것이 좋겠지만, 난이도가 급상승하고 직관적이지 못하다.
deque을 이용해서 시간 초과 문제를 어느 정도는 해결 가능하다!
메모리 사용량과 시간은 아래를 참고. 위가 ‘deque’을 이용한 방법, 아래가 ‘홀짝성’을 이용한 방법.

2164 결과

참고!

n에 따른 정답 (n, ans) 순서쌍 참고.