개요

링크

백준 2164번 : 카드 2

입력 예시

6

출력 예시

4

접근 방식

1. list

2. dequeue

Dequeue(덱)
양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다.
두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다.
간단하게 말하자면, 큐와 스택을 합친 형태이다.
출처 : https://ko.wikipedia.org/wiki/%EB%8D%B1_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

풀이

1. list

결과값 출력은 문제 없지만,
list의 pop(0)은 시간 복잡도가 O(N)이기 때문에 시간 초과가 발생한다.
따라서 list를 큐로 사용하는 것은 매우 좋지 못한 방법이다.

N = int(input())
cards = [i for i in range(1, N+1)]

while(len(cards) > 1) : 
    cards.pop(0)
    cards.append(cards.pop(0))

print(cards[0])

2. dequeue

파이썬에서 dequeue를 사용하기 위해선 collections library를 import 해주어야 한다.
dequeue에선 pop() 대신 popleft()를 사용하고,
원소를 추가할 땐 list와 마찬가지로 append()를 사용한다.

from collections import deque

N = int(input())
cards = deque([i for i in range(1, N+1)])

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

print(cards[0])

결과

위가 dequeue를 사용한 결과,
아래가 list를 사용한 결과이다.