백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2164 카드2 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/2164

반응형

솔루션 살펴보기!!

from collections import deque

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

while len(queue) > 1:
    queue.popleft()  # 첫 번째 요소를 버림
    queue.append(queue.popleft())  # 두 번째 요소를 맨 뒤로 이동

print(queue[0])

상세 코드 설명!!

이 코드는 주어진 숫자 N에 대해 1부터 N까지의 숫자를 순서대로 큐에 넣고, 특정 규칙에 따라 숫자를 제거하며 마지막 남은 숫자를 출력하는 알고리즘을 구현한 것입니다. 이 코드는 조세푸스 문제(Josephus Problem)와 유사한 방식으로 동작합니다.

코드 구조 및 주요 개념

deque를 사용한 큐 구현

• deque: Python의 collections 모듈에서 제공하는 deque는 양방향 큐로, 양쪽 끝에서 빠르게 요소를 추가하거나 제거할 수 있는 자료구조입니다. 이 자료구조는 FIFO (First-In-First-Out) 방식으로 큐를 구현할 때 유용합니다.
• 이 코드에서는 deque를 사용하여 큐를 초기화하고, popleft() 메서드를 사용하여 큐의 첫 번째 요소를 제거합니다. append() 메서드를 사용하여 큐의 끝에 요소를 추가합니다.

큐의 초기화

queue = deque(range(1, N + 1))

- range(1, N + 1)를 사용하여 1부터 N까지의 숫자를 생성한 뒤, 이를 deque로 초기화합니다. 이로써 1부터 N까지의 숫자가 큐에 순서대로 담기게 됩니다.

루프를 통한 숫자 제거

while len(queue) > 1:
    queue.popleft()  # 첫 번째 요소를 버림
    queue.append(queue.popleft())  # 두 번째 요소를 맨 뒤로 이동

 

• while len(queue) > 1:: 큐에 요소가 하나만 남을 때까지 루프가 실행됩니다.
• 첫 번째 숫자 제거: queue.popleft()로 큐의 첫 번째 숫자를 제거합니다.
• 두 번째 숫자 재배치: queue.popleft()로 다시 첫 번째 숫자를 제거한 후, 이 숫자를 queue.append()를 사용해 큐의 끝에 추가합니다. 이렇게 함으로써 매번 큐의 두 번째 숫자를 큐의 끝으로 옮기고, 첫 번째 숫자는 제거됩니다.

마지막 숫자 출력

print(queue[0])

 

• 루프가 끝나면 큐에 단 하나의 숫자만 남게 되는데, 이 숫자를 출력합니다.

728x90

주요 개념

1. 큐 (Queue):
   • 큐는 데이터를 일렬로 관리하는 자료구조로, FIFO(First In, First Out) 방식으로 작동합니다. 먼저 들어간 데이터가 먼저 나오는 구조입니다. 큐의 주요 연산은 데이터 추가(enqueue)와 데이터 제거(dequeue)입니다.
2. popleft() 연산:
   • deque에서 popleft()는 큐의 맨 앞에 있는 요소를 제거하고 반환합니다. 이는 O(1)의 시간 복잡도로 매우 효율적입니다.
3. append() 연산:
   • deque의 append()는 큐의 끝에 새로운 요소를 추가합니다. 이 역시 O(1)의 시간 복잡도를 가지며 효율적입니다.
4. 조세푸스 문제:
   • 이 문제는 사람들이 원형으로 앉아 있는 상황에서 특정 간격으로 사람을 제거해 나가는 고전적인 퍼즐 문제입니다. 이 코드는 그와 유사한 방식으로 큐에서 숫자를 제거하는 과정을 구현한 것입니다.