[Python/백준] 2164. 카드2

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

큐, 덱

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

---

풀이

# 1차 풀이, 최적화 안됨
from collections import deque
import sys

input = sys.stdin.readline

# 입력 : 카드 개수를 의미하는 정수 N (1 <= N <= 50만)
# 출력 : 남게 되는 카드의 번호 정수

# 1번 카드가 제일 위에, N번 카드가 제일 아래.
# ex. N = 3일 때
# 1
# 2
# 3
# 대충 1 2 3으로 생각하면 될듯.

# 아래 동작을, 카드가 한 장 남을 때까지 반복
# 1. 제일 위에 있는 카드를 바닥에 버림
# 2. 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮김

# ex. N = 3일 때
# 1. 1 2 3 4 5 -> 1 2 3 4
# 2. 1 2 3 4 -> 2 3 4 1

# 큐를 써서 풀어야 한다고 판단한 근거)
# '제일 위에 있는 카드를 바닥에 버린다'
# '제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다'
# 와 같이, ""양 끝단에서 데이터의 삽입과 추출이 이루어지고 있기에???""
# 따라서, 큐를 써서 풀어야겠다고 판단하는 것이다.
# 그리고 당연히 중간 조회보단 삽입 추출이 자주 일어나니
# 리스트가 아닌 덱을 써야함.

N = int(input())

# 카드 상태 초기화
# 큐의 앞에 있을수록 문제에선 위에 있는 카드라고 생각.

# queue = deque()
# for number in range(1, N + 1):
#     queue.append(number)

queue = deque(range(1, N + 1))
# 위 코드로 빠르게 초기화 가능.
# range 외에도 리스트, 문자열, 튜플, 셋 등의 iterator로 초기화 가능함.
# list()로 리스트 초기화해주는 것과 똑같이 생각하면 됨.

# 카드가 한 장 남을 때까지 반복

# for _ in range(N - 1):
while len(queue) > 1:
    # 1. 제일 위에 있는 카드 버리기
    queue.popleft()
    # 2. 제일 위에 있는 카드를 제일 아래로 옮기기
    queue.append(queue.popleft())

# print(*queue)
print(queue[0])

# 시간복잡도는 O(n * 1) = O(n) 정도로 보면 될듯.
# 입력이 최대 50만이니, 시간복잡도 측면에서도 OK!!


# 면접에서, 왜 덱으로 풀었냐고 묻는다면?

# 만약 queue로 풀었다면,
# 문제를 보니, 맨 위의 카드를 버리는 것과 맨 위의 카드를 아래로 옮기는 동작이
# 각각 pop(0)가 2번씩 포함되어 있다.

# 근데, 만약 list로 queue를 구현해 풀었다면,
# N이 50만까지 가능하므로, 최악의 경우로 50만장의 카드가 들어왔을 경우
# pop(0)은 대략 O(n)의 시간복잡도를 가지기에 50만번의 단위 연산이 합니다.

# pop(0)가 2개 있기에 반복문이 한 번 돌 때마다 거의 100만번 이상의 단위 연산이 소요됩니다.
# 해당 반복문이 50만번 반복될 것이므로,
# 100만 * 50만 = 5000만으로, 거의 5000만번의 단위 연산이 일어납니다.

# 그런데, 문제의 시간 제한이 2초이면 대략적으로 2억번의 단위 연산내에 풀어야 안정적이므로,


# 그런데, 덱의 경우는 pop(0) 대신 popleft()로 O(1)만에 해당 연산이 가능하므로,
# 약 O(n)의 시간복잡도로 해당 문제가 해결이 가능합니다.

# 따라서, 덱을 사용하였습니다.

---

250218 재풀이

from collections import deque
import sys
input = sys.stdin.readline

# n장 카드 1~n 번호
# 아래 동작을 카드가 한 장 남을 때까지 반복
# 1. 제일 위에 있는 카드를 버림
# 2. 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮김.

# 이거 덱(큐) 쓰는 문제네!

n = int(input())
queue = deque(range(1, n + 1))

for _ in range(n - 1):
    # 1. 제일 위에 있는 카드 버림
    queue.popleft()

    # 2. 제일 위에 있는 카드 제일 밑으로 옮김
    queue.append(queue.popleft())

print(queue[0])