[boj 2164.python] '카드2' 풀이 (시간초과 해결)

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

접근 방식

처음에 문제 읽자 마자, 쉬운 구현 문제라고 생각하고 냅다 단순 리스트로 풀어버렸다.

 

1차 코드 (리스트 사용) 👉 실패 ❌

N = int(input())

# 카드 리스트 생성
card = [i + 1 for i in range(N)]

# 카드 섞기
def card_mix():
    while len(card) > 1:   # 카드가 한 장 남을 때까지 반복
        # 제일 위에 있는 카드 바닥에 버림
        card.pop(0)
        # 그 다음 위에 있는 카드는 제일 아래에 있는 카드 밑으로 옮김
        card.append(card[0])
        card.pop(0)
    print(card[0])

card_mix() # 함수 호출

 

카드묶음을 리스트로 생성하고, 카드 섞기 함수를 만들어 호출한 간단한 코드였다.

결과는?

 

★ 시간초과 엔딩 ★

 

보자마자 엥? 왜 시간 초과가 났지 하고 바로 아까는 확인하지 못했던 (..) 제한 조건을 확인하러 갔다.

그렇다 N은 최대 500,000 까지 입력될 수 있었다.

 

시간 초과가 나는 이유 

이 코드에서 시간초과가 발생하는 이유는 리스트의 pop() 연산 때문이다. 

파이썬의 리스트는 동적 배열 구조를 사용하므로, 리스트의 맨 앞 요소를 제거하는 pop(0)은 모든 요소를 앞으로 한 칸씩 이동시키는 작업을 수행한다. 

따라서 pop(0) 연산의 시간 복잡도는 O(N) 이다.

 

카드 리스트의 길이가 N에서 1까지 줄어들면서 반복문은 대략 N - 1번 수행되는데, 각 반복에서 pop(0)을 호출하고 있으므로 전체 시간 복잡도는 O(N^2)가 되는 것이다.

 

문제의 제약 조건에서 N <= 500,000이므로, 이 알고리즘은 비효율적이고 시간 초과가 발생할 수 밖에 없는 것.

 

해결 방법

시간 초과를 해결하기 위해선 'Queue' 자료구조를 쓰면 된다. 

파이썬에서 일반적인 자료구조 문제를 풀 때는 deque라는 컬렉션을 쓰게 되는데,deque는 "double-ended que"의 약자로 스택과 큐를 일반화 한 것이다.

 

deque는 양쪽 끝에서의 삽입과 삭제가 모두 O(1) 연산이기 때문에 시간초과 이슈 없이 문제를 효율적으로 해결할 수 있다.

 

2차 코드 (deque 사용) 👉 성공 ⭕

from collections import deque
N = int(input())

# 카드 큐 생성
card = deque(range(1, N + 1)) # deque([1, 2, 3, 4, 5, 6])

# 카드 섞기
def card_mix():
    while len(card) > 1:   # 카드가 한 장 남을 때까지 반복
        # 제일 위에 있는 카드 바닥에 버림
        card.popleft()
        # 그 다음 위에 있는 카드는 제일 아래에 있는 카드 밑으로 옮김
        card.append(card.popleft())
    print(card[0])

card_mix() # 함수 호출

 

1번 코드와 로직은 똑같다. deque(range(1, N + 1))로 1부터 N까지의 숫자를 큐에 저장해서, 카드의 제거와 삽입을 O(1) 복잡도로 해결할 수 있다는 것만 다름 ..ㅎㅎ

 

여기서의 popleft()와 append()는 각각 O(1) 이므로, N − 1번의 반복에 대해 총 O(N) 시간이 걸린다.

성공 !

 

결론

리스트 기반의 O(N^2) 알고리즘 대신 O(N) 알고리즘으로 최적화를 시켜보았다.

꼭 문제풀 때 제한사항을 확인하자 ^-^!! 🥲