[백준 2164번 문제] 카드2

이 문제는 큐의 원리를 응용한 문제이다.

입력받은 숫자만큼의 카드가 1부터 있고 맨앞에 있는 카드를 없앤 후에 나머지 카드 중 맨앞에 있는 카드를 맨위로 옮기는 방식이다. 이렇게 카드가 1개가 남을 때까지 반복한 후에 1장 남은 카드의 숫자를 출력하면 된다.

 

<해결방법>

먼저 for 반복문을 이용해서 1부터 입력받은 N까지의 숫자카드를 빈 리스트에 저장해주었다.

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

그 다음 아래와 같은 원리로 카드놀이가 진행된다.

123456

23456->34562

4562 -> 5624

624 -> 246

46 -> 64

4

맨앞에 있는 숫자를 pop시키고 모든 숫자를 왼쪽으로 옮겨주는 과정을 어떻게 구현할까 고민했었는데 며칠전에 풀었던 deque를 이용해서 popleft메소드를 사용하였다.

그 다음에 맨 앞에 있는 숫자를 맨위로 옮겨주어야하는데 처음엔 card[-1] = card[0] 이런 방식으로 코드를 짰더니 추가가 되는게 아니라 맨 마지막 숫자가 대체되는 에러를 간과하였다.

그래서 append메소드를 이용해서 처리한 후에 다시 popleft를 하였다.

for i in range(n-1):
    card.popleft()
    card.append(card[0])
    card.popleft()

맨앞에꺼 없애기 ==  deque([2, 3, 4, 5, 6])
맨앞에꺼 맨뒤로 옮기기 ==  deque([3, 4, 5, 6, 2])
맨앞에꺼 없애기 ==  deque([4, 5, 6, 2])
맨앞에꺼 맨뒤로 옮기기 ==  deque([5, 6, 2, 4])
맨앞에꺼 없애기 ==  deque([6, 2, 4])
맨앞에꺼 맨뒤로 옮기기 ==  deque([2, 4, 6])
맨앞에꺼 없애기 ==  deque([4, 6])
맨앞에꺼 맨뒤로 옮기기 ==  deque([6, 4])
맨앞에꺼 없애기 ==  deque([4])
맨앞에꺼 맨뒤로 옮기기 ==  deque([4])

위와 같이 진행하면 card라는 리스트안에 이런식으로 숫자가 남게된다!

 

<전체코드>

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
card = deque([])

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

for i in range(n-1):
    card.popleft()
    # print("맨앞에꺼 없애기 == ", card)
    card.append(card[0])
    card.popleft()
    # print("맨앞에꺼 맨뒤로 옮기기 == ", card)
print(card[0])