백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2346 풍선 터뜨리기 편 (python)

문제 살펴보기!!

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

솔루션 살펴보기!!

from collections import deque

def main():
    # 입력 처리
    N = int(input())
    queue = deque(map(int, input().split()))
    index_queue = deque(range(1, N + 1))  # 1부터 N까지의 숫자 큐 생성

    while queue:
        steps = queue.popleft()  # 현재 큐의 첫 번째 요소를 꺼냄
        if steps > 0:
            queue.rotate(-(steps - 1))  # 양수일 때 회전
            print(index_queue.popleft())  # 원래 위치 인덱스 출력
            index_queue.rotate(-(steps - 1))  # 인덱스 큐 회전
        else:
            queue.rotate(-steps)  # 음수일 때 회전
            print(index_queue.popleft())  # 원래 위치 인덱스 출력
            index_queue.rotate(-steps)  # 인덱스 큐 회전

if __name__ == "__main__":
    main()

반응형

코드 내용 및 흐름 설명

이 코드는 큐(deque)를 사용하여, 특정 순서에 따라 사람들을 원형으로 회전시키며 제거하는 문제를 해결합니다. 이 문제는 종종 "요세푸스 문제(Josephus Problem)"로 알려져 있습니다. 코드를 하나씩 살펴보겠습니다.

1. 입력 처리 및 큐 생성

N = int(input())  # N은 사람의 수를 나타냅니다.
queue = deque(map(int, input().split()))  # 각 사람에 대한 이동 수를 나타내는 큐를 생성합니다.
index_queue = deque(range(1, N + 1))  # 1부터 N까지의 사람의 위치를 나타내는 큐를 생성합니다.

 

• queue: 각 사람마다 이동할 거리가 주어집니다. 이 큐는 이 이동 거리를 담고 있습니다.
• index_queue: 1부터 N까지의 숫자가 들어있는 큐입니다. 각 숫자는 사람의 초기 위치를 나타냅니다.

2. 메인 로직 - 원형 회전하며 제거

while queue:
    steps = queue.popleft()  # 큐의 첫 번째 요소를 꺼내 이동 거리를 가져옵니다.
    if steps > 0:
        queue.rotate(-(steps - 1))  # 이동 거리가 양수인 경우 큐를 회전시킵니다.
        print(index_queue.popleft())  # 사람의 위치를 출력합니다.
        index_queue.rotate(-(steps - 1))  # 인덱스 큐도 동일하게 회전시킵니다.
    else:
        queue.rotate(-steps)  # 이동 거리가 음수인 경우 큐를 회전시킵니다.
        print(index_queue.popleft())  # 사람의 위치를 출력합니다.
        index_queue.rotate(-steps)  # 인덱스 큐도 동일하게 회전시킵니다.

• steps: 현재 사람의 이동 거리를 나타냅니다. queue.popleft()로 꺼내 사용합니다.
• 양수 이동 (steps > 0):
  • 큐를 왼쪽으로 (steps - 1)만큼 회전시킵니다.
  • 원래 위치를 나타내는 index_queue에서 첫 번째 사람을 꺼내 출력하고, 동일하게 회전시킵니다.
• 음수 이동 (steps <= 0):
  • 큐를 왼쪽으로 steps만큼 회전시킵니다. 음수이므로 결과적으로 오른쪽으로 회전하는 효과가 있습니다.
  • 인덱스 큐도 동일하게 회전시킵니다.

3. 출력

• 각 회전에서 제거되는 사람의 원래 위치(1부터 N까지의 숫자)를 출력합니다.

728x90

알아야 할 주요 개념

1. 큐(deque):
   • 큐는 선입선출(FIFO, First-In-First-Out) 구조로 데이터를 처리합니다.
   • deque는 양방향 큐로, 양쪽에서 삽입과 삭제가 모두 O(1) 시간 복잡도로 이루어집니다.
   • popleft()는 왼쪽에서 데이터를 꺼내는 함수입니다.
   • rotate(n)은 큐의 데이터를 n만큼 회전시키는 함수입니다. 양수이면 오른쪽으로, 음수이면 왼쪽으로 회전시킵니다.
2. 회전(rotate):
   • 이 코드는 회전 기능을 사용해 큐의 순서를 바꾸면서 작업을 수행합니다. 회전은 요소들을 이동시키면서 다음에 처리할 요소를 정하는 데 사용됩니다.
3. 요세푸스 문제:
   • 고대 유대인의 전쟁 이야기에서 유래한 문제로, 이 코드와 유사하게 특정 간격으로 사람들을 제거하면서 마지막 남는 사람을 찾는 문제입니다.
   • 이 문제는 자료 구조와 알고리즘의 연습으로 자주 사용됩니다.
4. 조건 분기:
   • 양수와 음수에 따라 다른 회전 및 인덱스 처리 방법이 적용되므로, 이 코드는 조건 분기를 통해 두 가지 경우를 다르게 처리합니다.

이 코드는 큐의 기본적인 사용법과 회전이라는 개념을 잘 활용하여 문제를 해결합니다. 이 개념들은 알고리즘 문제에서 자주 등장하는 중요한 요소들입니다.