2학년 2학기 알고리즘 과제_4주차(백준_2346번:풍선 터뜨리기)

2346번: 풍선 터뜨리기

 

 

문제

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

 

 

📌 내풀이

일단 문제를 살펴보면, 1번부터 2번 3번 N번까지 N개의 풍선이 원형으로 놓여있고, i번 풍선, 예를 들어 2번의 오른쪽에는 3번이 놓여있고, 왼쪽에는 1번이 놓여있을 것이다. 단, 1번 풍선의 왼쪽에는 N번 풍선이 있고, N번 풍선의 오른쪽에는 1번 풍선이있다.

그림을 그려보면서 풀어보면 이해가 쉬울 것 같아서 그림을 그리며 풀었다.

 

이 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있는데, 규칙을 가지고 풍선을 터뜨릴 것이다.

 

우선 제일 처음에는 1번풍선을 터뜨리는데, 다음에는 풍선 안에 종이를 꺼내 그 종이에 적혀있는 값만큼 이동해서 다음 풍선으 터뜨린다. 양수가 적혀있을 경우 오른쪽, 음수가 적혀있는 경우에는 왼쪽으로 이동함 이동할 때에는 이미 터진 풍선은 제외한다.

 

다섯개의 풍선 안에 차례로 3,2,1,-3,-1이 적혀있을 때, 3이 적혀있는 1번 풍선, -3이 적혀있는 4번 풍선, -1이 적혀있는 5번 풍선, 1이적혀 있는 3번 풍선, 2가 적혀있는 2번 풍선 순서대로 터질 것이다.

 

이 문제를 풀기위해선, 덱의 기본구조를 이용해야할 것 같다. 덱의 기본구조를 배울 때, 원형을 배운 적이 있는데, 이를 이용하면 될 것 같다.

 

 

[자료구조] 덱(DEQUE)

[자료구조] 덱(DEQUE)

 

 

 

 

덱은 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조이다.

• 특징
  -스택과 큐 자료구조를 혼합한 자료구조이다.
  -스택이나 큐보다 입출력이 자유로운 자료구조이다.
  -덱은 double-ended queue의 줄임말이다.
  -전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐이다.
  -하지만 여전히 중간에 넣거나 빼지는 못한다.
  -파이썬의 리스트나 이중연결리스트로 구현 가능

 

 

📌 코드 분석

 

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())

deq = deque(enumerate(map(int, input().split())))
answer = []

while deq:
    idx, now_turn = deq.popleft()
    answer.append(idx + 1)

    if now_turn > 0:
        deq.rotate(-(now_turn - 1))
    elif now_turn < 0:
        deq.rotate(-now_turn)

print(' '.join(map(str, answer)))

 

 

• sys.stdin.readline을 사용해 입력을 빠르게 받으며, 첫 번째 입력값은 풍선의 개수 n이다.
• 두 번째 줄의 입력은 풍선 안에 적힌 숫자 리스트이다.
• enumerate 함수를 사용해 각 숫자와 인덱스 정보를 함께 deque에 저장하는데, 여기서 deque는 인덱스와 풍선의 숫자를 함께 튜플로 저장하도록 한다.
• 터진 풍선의 순서를 저장할 리스트 answer를 초기화한다.
• while 루프는 덱에 남아있는 풍선이 없을 때까지 반복되도록한다.
• deq.popleft()로 덱의 첫 번째 요소를 꺼내 (idx, now_turn)에 저장하며 여기서 idx는 풍선의 인덱스, now_turn은 이동할 칸 수를 의미한다.
• answer.append(idx + 1)로 터진 풍선의 인덱스를 answer에 추가하는데, 여기서 1을 더하는 이유는 인덱스가 0부터 시작하기 때문이다.
• 풍선이 터진 후에는 now_turn 값에 따라 덱을 회전시킨다.
• now_turn이 양수인 경우, deq.rotate(-(now_turn - 1))을 통해 왼쪽으로 now_turn - 1만큼 회전하도록한다.
• now_turn이 음수인 경우, deq.rotate(-now_turn)을 통해 오른쪽으로 now_turn만큼 회전하도록한다.
• 최종적으로 answer 리스트의 값을 공백으로 구분해 출력하도록 한다.

 

 

요약

 

• 첫 번째 풍선부터 시작하여, 현재 풍선의 숫자에 따라 다음 풍선의 위치로 이동한다.
• 이동한 위치에서 풍선을 터트리고, 그 위치의 숫자에 따라 다시 이동을 반복한다다.
• 모든 풍선이 터질 때까지 이 과정을 반복하고, 터진 순서를 answer 리스트에 기록해 출력한다.

 

 

 

 

 

📌 느낀점

 

 

덱이라는 자료구조는 자료구조시간에 학습한 경험이 있는데, 기본 구조를 활용하는데에 대한 이해는 조금 생긴 것 같다.

완벽히 구현할 수는 없지만, 조금씩 자료구조를 어떤식으로 접근할지 아주 약간은 아이디어가 생기는 기분이 들었다.

 

 

 

 

[ 참고 자료 ]

 

[백준] 2346번 : 풍선 터뜨리기 (스택/큐(덱) 실버Ⅲ) - Python — 채야미의 코드레시피🍳

[백준] 2346번 : 풍선 터뜨리기 (스택/큐(덱) 실버Ⅲ) - Python