백준 2164번 - 카드2 - 파이썬(Python)

문제 링크

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

문제

 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

 

입력 조건

• 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력 조건

• 첫째 줄에 남게 되는 카드의 번호를 출력한다.

입력 예시

6

출력 예시

4

 

풀이 전 생각

 크게 생각해야할 부분은 없는 것 같고 문제에서 주어진 대로 코드를 작성하면 해결될 것 같다. 

 

예제 코드(시간 초과)

n=int(input())
list = [i+1 for i in range(n)]
while(len(list)!=1):
    del list[0]
    temp = list[0]
    del list[0]
    list.append(temp)
print(list)

 

위 코드와 같이 리스트를 이용해 문제를 풀게되면 시간초과가 발생한다. 

시간초과를 해결한 코드는 아래와 같고 이유에 대해서는 포인트에 작성하였다.

예제 코드

from collections import deque

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

while(len(deque) > 1):
    deque.popleft()
    move_num = deque.popleft()
    deque.append(move_num)

print(deque[0])

포인트

 처음 list로 작성한 코드가 시간 초과가 나는 이유와 deque을 사용했을 때 해결되는 이유에 대해 분석해보려고 한다.

     (list를 사용했을 때, 시간 초과 이유)

리스트(list)는 동적 배열(Dynamic Array) 구조로 되어 있다.
파이썬 리스트는 연속된 메모리 블록에 데이터를 저장하므로, 특정 인덱스의 요소를 삭제하면 뒤에 있는 모든 요소를 한 칸씩 앞으로 이동해야 한다.

예제: del list[0] 수행 과정

list = [1, 2, 3, 4, 5] del list[0] # 첫 번째 요소 제거

이후 리스트 내부에서 발생하는 동작:

1. [ 1, 2, 3, 4, 5 ] # 초기 리스트

2. [ _, 2, 3, 4, 5 ] # 첫 번째 요소 제거됨 (_는 빈 공간)

3. [ 2, 3, 4, 5 ] # 나머지 요소들이 한 칸씩 앞으로 이동

• 요소 이동이 N개 데이터에 대해 매번 발생 → O(N)
• 만약 리스트의 크기가 1,000,000이라면 한 번 del list[0] 할 때 최대 999,999번 이동해야 한다.
• while 루프에서 계속 del list[0]을 실행하면 O(N²) 이 된다.

    (deque을 사용했을 때, 해결되는 이유)

collections.deque는 이중 연결 리스트(Doubly Linked List) 기반의 자료구조이다.

• 리스트와 달리 메모리가 연속적이지 않고, 각 요소가 앞뒤 요소를 가리키는 포인터를 가지고 있음.
• 따라서 popleft()를 하면 첫 번째 노드의 참조만 변경하면 되므로, 요소 이동이 필요 없음.

예제: deque.popleft() 수행 과정

 

from collections import deque

dq = deque([1, 2, 3, 4, 5])

dq.popleft()

이후 deque 내부 동작:

1. [ 1 <-> 2 <-> 3 <-> 4 <-> 5 ] # 초기 deque

2. [ 2 <-> 3 <-> 4 <-> 5 ] # 첫 번째 노드 제거 (연결만 변경됨)

• 요소를 삭제해도 나머지 요소들을 이동할 필요 없다. → O(1)
• while 루프에서 popleft()를 계속 실행해도 전체 연산이 O(N) 에 그친다.

 

생각

 '그렇다면 큐에 비해서 속도도 훨씬 빠르고, 앞뒤 모두 삽입/삭제가 가능한 덱만 사용하면 되는 거 아니야?' 라는 의문이 들지만 꼬리에 꼬리를 물면 끝이 없을 것 같기에 *나중에 자료구조에 내용을 정리하도록 하자.