이 문제는 보자마자 느낌이 온다.
큐 자료구조를 이용하는 문제이다.
주의할 것은 입력 범위가 크다는 것이다.
문제를 풀기 위해서는 반복문 사용이 필수적이다.
때문에 시간 복잡도를 신경쓰며 문제를 풀어야 한다.
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
문제 풀이
출력을 내는 방법은 그리 어렵지 않다.
문제의 예시와 같이 N=4라고 가정하고 문제를 분석해보겠다.
우선 N장의 카드가 주어지면 1부터 N까지 순서대로 카드를 놓는다. (N이 맨 아래에 있는 상태)
① 제일 위에 있는 카드를 바닥에 버린다.
② 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
이 과정(①, ②)을 카드가 한 장 남을 때까지 반복한다.
카드가 한 장 남으면 해당 카드의 숫자를 출력한다.
실험 정신
사실 이 문제는 큐를 사용하지 않아도 풀수는 있다.
단지 시간이 더 걸릴 뿐이다.
아래의 코드는 실험 정신으로 큐를 사용하지 않고 리스트로 구현 후 제출하였다.
결과는? 당연히 시간 초과.
n = int(input())
cards = list(range(1, n+1))
while(len(cards)!=1):
cards.pop(0)
move = cards.pop(0)
cards.append(move)
print(cards[0])위의 코드가 왜 문제인지 모르는 사람을 위해 추가로 설명하자면, 리스트의 삽입/삭제 과정에 일어나는 일 때문이라고 말할 수 있겠다.
위의 그림에서 리스트 맨 앞에 있던 1이 삭제 되었다. 그냥 삭제되고 끝일까?
리스트의 중간 데이터를 삭제하면 앞뒤 인덱스 데이터가 스르륵 하고 붙는걸까?
아니다. 내부적으로는 추가적인 일이 일어나고 있었다.
pop(0)으로 1을 지웠으므로 1, 2, 3번 인덱스에 있던 데이터를 한 칸씩 앞으로 땡겨줘야 한다.
데이터를 중간에 삽입하는 것도 비슷한 과정으로 진행된다.
이러한 경우 삽입/삭제되는 인덱스 뒤의 데이터 개수가 N개라면 N번의 데이터 이동이 일어나야 하므로 O(N)의 시간 복잡도를 가진다.
카드가 한 장만 남을때까지 반복하며 삭제를 할 뿐만 아니라 데이터를 앞으로 땡겨줘야 했기 때문에 시간 초과가 났던 것이다.
해결 방법
collections 모듈의 deque를 사용하였다.
deque는 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.
deque는 popleft()와 appendleft(x) 메서드를 제공한다.
popleft()와 appendleft(x) 메서드는 모두 O(1)의 시간 복잡도를 가진다.
from collections import deque
n = int(input())
cards = deque(range(1, n+1))
while(len(cards)!=1):
cards.popleft()
move = cards.popleft()
cards.append(move)
print(cards[0])+) 추가
deque는 random access의 시간복잡도가 O(N)이다.
내부적으로 linked list를 사용하고 있기 때문.
때문에 N번째 데이터에 접근하려면 N번의 순회가 필요하다.
카드2 문제에서는 양 끝 데이터만을 이용했으므로 문제는 없었지만, 중간에 있는 데이터에 접근이 필요한 문제라면 조금 더 주의를 기울여 사용해야 할 것 같다.
참고자료
파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O)
Complexity of Python Operations
파이썬에서 큐(queue) 자료구조 사용하기
