[Python] 백준 2164 - 카드2

백준 2164 - 카드2

https://www.acmicpc.net/problem/2164

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

해결 방법

• 1 부터 N까지의 카드를 덱에 저장한다.

• while문을 이용해서 덱에 카드가 한장만 남아있을 때 까지 popleft() 와 append(popleft()) 를 반복한다.

왜 큐가아닌 덱을 사용할까?

왼쪽의 값을 가져와 오른쪽에 추가하는 구현은 큐도 할 수 있는데 왜 덱을 사용할까 라는 의문이 들 수도 있다.

이유를 알기 위해선 파이썬의 큐와 덱의 속도 차이에 대해 알 필요가 있다.

• 덱은 각 명령(push나 pop 등) 을 O(1) 으로 지원함
• 큐 모듈은 멀티쓰레드 환경을 지원함
• 따라서 덱이 큐보다 훨씩 속도가 빠름

이러한 이유로 인해 알고리즘 구현시 큐보다는 덱의 사용을 권장한다.

한 예시로 백준 1158 - 요세푸스 문제 (https://www.acmicpc.net/problem/1158) 는 큐로 구현하면 시간초과가 나지만 덱으로 구현하면 시간초과가 나지 않는다.

해결 코드

from collections import deque
import sys

deq = deque()
input = sys.stdin.readline

n = int(input())

for i in range(n):
    deq.append(i+1)

while len(deq) != 1:
    deq.popleft()
    deq.append(deq.popleft())

print(deq[0])

더 효율적인 해결방법

• 출력들 속에서 일정한 규칙을 발견해 공식화하는 것이다.

• 입력과 출력값을 모두 모아보면

  입력	출력
  2	2
  3	2
  4	4
  5	2
  6	4
  7	6
  8	8
  9	2
  10	4
  11	6
  12	8
  13	10
  14	12
  15	14
  16	16
  17	2

  위와 같이 규칙이 있는것을 확인할 수 있고,

  출력값 = ((입력값) - (입력값보다 작은 2n 의 최댓값)) * 2

  이라고 공식화할 수 있다.

  a = int(input())
  b = 2
  
  while True:
      if a == 1 or a == 2:
          print(a)
          break
      b *= 2
      if b >= a:
          print((a-(b//2))*2)
          break

  따라서 위와 같이 규칙을 찾아 공식화해 해결할 수도 있다.