문제 링크

개요

  • 큐를 이용하여 풀 수 있는 간단한 문제이다.
  • 양쪽에서 데이터를 빼고 집어넣는 작업이 요구되기 때문에 deque의 사용을 권장한다.
  • 1번 카드의 위치를 앞으로 하냐 뒤로 하냐는 크게 상관없기 때문에 앞에서부터 정의하겠다.

문제 해설

  • 문제에서 제시된 행동은 1. 제일 위의 카드를 버린다 2. 제일 위에 남은 카드를 제일 아래로 옮긴다 이다.
  • 해당 행동을 카드가 한 장이 남을 때까지 무한히 반복하면 된다.
  • 1번 행동을 하기 위해선 1번 카드를 큐의 맨 앞으로 정했기에 큐의 왼쪽에서 값을 빼내면 된다.
  • 큐의 왼쪽에서 값을 빼내기 위해 popleft() 함수를 사용한다.
  • 2번 행동은 마찬가지로 큐의 왼쪽에서 값을 빼내고, 추가로 빼낸 값을 맨 뒤에 추가한다.
  • 큐의 왼쪽에서 빼낸 값을 다시 넣어야 하기 때문에 append() 안에 popleft()를 넣어준다.
  • 두 가지 동작을 while문 안에 넣고 카드가 1개보다 많이 남으면 반복하도록 조건을 설정한다.
  • while문이 종료된 후 하나의 값이 남아있는 큐에서 pop()을 사용해 마지막 남은 카드를 출력한다.

시간 복잡도

  • 문제에서 주어진 시간은 2초다.
  • 가장 단순하게 리스트로 큐를 구현할 경우 del() 함수를 이용해 값을 삭제해야 할 것이고
    이를 N번 만큼 반복할 것이므로 이 때의 시간 복잡도는 O(N^2)를 초과한다.
  • N의 최댓값이 500,000이므로 대충 어림잡아도 연산 횟수가 2억을 훌쩍 초과한다.
  • 반면, deque로 큐를 구현한 해설의 경우 시간 복잡도가 O(1)인 popleft()를
    N번 만큼 반복하기 때문에 O(N)의 시간 복잡도를 가진다.
  • 이는 제한 시간 내에 충분히 수행하고도 여유가 남을 알고리즘이다.

해설 코드

1
2
3
4
5
6
7
8

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.pop())