백준 2164번 카드2 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 2164 카드2

2164 카드2

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

2164번: 카드2

deque 사용법이 익숙하지 않아 쉬운 문제로 접해보기 위해 풀이하였다. 상당히 쉬운 문제였다.

---

코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
q = deque()

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

while len(q) > 1:
    q.popleft()
    q.append(q.popleft())

print(q[0])

---

풀이

자료구조를 다루는 문제에서 deque의 필요성과 편의성을 알게 되어 사용해보고자 문제를 풀이하였다. deque는 양방향 큐로 활용 가능하다 즉 스택으로도 활용이 가능하다는 이야기이다. 기존의 선입선출(FIFO) 방식에 비하면 활용성이 더 좋다. 또한 append와 pop 기능이 아주 빠르게 연산된다고 한다. (deque의 rotate 메서드를 활용하면 알고리즘 풀이에 많은 도움이 될 것 같다.)

사용법은 우선 모듈을 import 하고 deque의 메서드를 활용할 리스트를 deque로 선언해주어야 한다.

from collections import deque
q = deque()

이제 풀이로 넘어가자면 q[0]이 가장 위로 가정하고 q[n]이 가장 밑이라 하면 for문을 활용해 1번부터 n번까지의 리스트를 q에 append 한다. 이후에는 while문을 q에 값이 하나 남을 때까지 loop을 돌려준다.

가장 위의 카드를 버리고 그다음 위의 카드를 맨 밑으로 추가하여야 하므로 맨 위는 리스트 가장 왼쪽이므로 popleft 메서드를 사용하고 맨 밑으로 추가하려면 append이지만 버린 카드 다음으로 맨 위의 카드를 빼면서 오른쪽에 추가한다. q리스트 안에 1개의 요소만 남아있으면 while문은 끝나고 q[0]을 출력하면 된다.

---

풀이 결과

2164 풀이결과