2164. [Python] 카드2

1. 문제

 

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

2164번: 카드2

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 큐

 

3. 파이썬 코드

 

from collections import deque

N = int(input())
# 카드 리스트를 deque로 선언
card_list = deque()
# 1~N 까지 카드 리스트 생성
for i in range(1,N+1):
    card_list.append(i)
# card의 길이 변수로 생성
card_length = len(card_list)
# 카드 길이가 1일때 까지 반복
while card_length > 1:
    # 카드 길이의 왼쪽 값을 뽑아옴
    card_list.popleft()
    # 카드에서 한번더 왼쪽 값을 뽑아서 변수에 저장
    check = card_list.popleft()
    # 뽑은 값을 오른쪽에 추가
    card_list.append(check)
    # 한번 시행했으므로 카드 길이 -1 해줌
    card_length -= 1
print(card_list[0])

 

4. 문제를 풀고난 후 생각

 

• 리스트를 순회하며 처음 카드를 뽑고 한번 더 뽑아서 제일 아래로 내리는 구조를 반복하는 코드이다.
• 리스트를 선입선출 하는 방식의 구조로 큐(Queue)를 사용해서 해결해야 하는 문제이다.
• Python 에는 Deque 라는 함수로 시작부터 값을 뽑을 수 있는 편리한 함수가 있다. (시간 복잡도 O(1)로 낮다)
• 이를 활용하여 코드를 간단하게 구현하였다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• Deque