[백준] 2164 카드 2

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

2164번: 카드2

문제를 해석해보자

 

N장의 카드가 있다. 카드는 1부터 N까지의 번호가 붙어있으며, 1번카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여있다. 다음 두개 동작을 지속적으로 수행하며 한장 남을때 까지 반복하게 된다. 두가지 동작은 아래와 같다

1. 가장 위에 있는 카드를 버린다
2. 가장 위에 있는 카드를 카드의 마지막으로 옮긴다

N이 주어졌을때 제일 마지막에 남는 카드를 구하시오

 

결론적으로 1번 행동은 pop만 수행하게 되는것이고, 2번 행동은 pop을 한 후에 append를 하는 행동이다. 두가지 방법으로 접근해 보았다. 하는 일반적인 반복문으로,하나는 재귀적 방법으로다. 재귀적 방법은 백준 서버에서 RuntimeError, Memory Error(재귀 허용범위를 해제하고)을 냈지만, 접근해 본것에 의의를 둔다.

 

< 일반적인 반복문으로 접근하기 >

import sys
from collections import deque
from typing import Any, MutableSequence

def solution(a : deque):
    while len(a) != 1:
        a.popleft()
        a.append(a.popleft())
    return a[0]

if __name__ == "__main__":
    print(solution(deque([i + 1 for i in range(int(sys.stdin.readline()))])))

< 재귀적 방법으로 접근하기 > 

import sys
from collections import deque
from typing import Any, MutableSequence

# 백준에서는 recursion error가 뜨지만 재귀로 작성해본 코드

def solution(a : deque):
    if len(a) == 1:
        return a[0]
    else:
        a.popleft()
        a.append(a.popleft())    
        return solution(a)
      
if __name__ == "__main__":
    print(solution(deque([i + 1 for i in range(int(sys.stdin.readline()))])))