백준 2346번 : 풍선 터뜨리기(S3)

 

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

2346번: 풍선 터뜨리기

 

✨ 문제

• 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.
• 우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

 

✨ 접근 방법

 

- 결론부터 이야기하자면 결국 이 문제를 푸는데 실패했다 ㅠㅠㅠ 몇시간 동안 고민한 결과 어느정도 정답에 근접했지만 결국 실패해버리고 다른 사람의 정답을 참고했다.

 

- 처음 이 문제를 접했을 때는 큐를 먼저 떠올렸다. 리스트를 쓸 수도 있겠지만, 이 문제에서는 지속적인 pop이 이루어지고 이를 파이썬의 list로 구현한다면 시간복잡도가 올라갈 것이라고 생각했다. 왜냐하면 파이썬의 list는 array list를 쓰기에 앞의 원소가 pop 되면 뒤의 원소들은 index를 하나씩 앞으로 당기게 되면서 시간 복잡도가 O(n)이 되기 때문이다.

 

- 그래서 큐를 통해 문제를 해결하고자 하였지만 다른 고민이 생겼다. 우리는 풍선을 인덱스로 접근해야하는데, 큐에서는 인덱스를 통한 pop이 불가능하다는 것!!! 그래서 생각한 대안은 index에 해당하는 값을 저장한 후 remove 함수를 이용하는 것이었다. 하지만 이는 만약 풍선에서 중복된 값이 있을 경우 불가능해진다. 문제에는 중복을 불허한다는 내용이 없으므로 이 방법도 불가능이다.

 

- 큐를 포기하고 리스트로 구현을 시작했다. 풍선에 적힌 값을 기록하기 위한 리스트와, 풍선의 인덱스를 기록하기 위한 리스트 이렇게 두 개의 리스트를 만들었다. 추가로 remove_index, op(operation) 등과 같은 변수를 만들어서 이런저런 방법을 시도해봤지만 실패 ㅋㅋㅋ큐ㅠㅠㅠ

 

- 결국 다른 사람의 코드를 보았는데 deque의 rotate기능을 이용해서 아주 쉽게 구현이 가능한 문제였다...

 

- 그렇다면 deque의 rotate 함수는 어떤 기능을 할까?

 

 

✨ Deque의 rotate

- rotate라는 이름에서 유추 가능하듯이 rotate함수는 큐의 원소를 지정한 개수만큼 회전시키는 기능을한다. 기본적으로 원소를 오른쪽으로 돌리며 인자로 음수 값을 주면 왼쪽으로 돌리게 된다.

 

- 아래 코드의 예시를 보면 원래 [1,2,3,4,5] 였던 큐를 오른쪽으로 2번 회전하여 모든 요소가 오른쪽으로 두 칸 이동하게 되고 결과적으로 [4,5,1,2,3,]의 결과를 보인다. 이렇게 회전된 큐를 또 다시 -3만큼 회전시키면 왼쪽으로 3칸 이동시키는 것이므로 [2,3,4,5,1]과 같은 결과를 보이게 되는 것이다.

from collections import deque

# 덱 생성
my_deque = deque([1, 2, 3, 4, 5])

# 현재 덱 상태 출력
print("Original deque:", my_deque)

# 오른쪽으로 2번 회전
my_deque.rotate(2)
print("After rotating 2 to the right:", my_deque)
#After rotating 2 to the right: deque([4, 5, 1, 2, 3])

# 왼쪽으로 3번 회전
my_deque.rotate(-3)
print("After rotating 3 to the left:", my_deque)
#After rotating 3 to the left: deque([2, 3, 4, 5, 1])

 

 

 

 

✨ 코드

- 이제 deque의 rotate 기능을 이용하면 아주 쉽게 문제를 풀 수 있다

 

from collections import deque

N = int(input())
queue = deque(list(map(int, input().split())))
queue2 = deque([i for i in range(1,N+1)])

answer = []

while queue:
    q = queue[0]
    print(queue)
    if q > 0:
        queue.popleft()
        queue.rotate(-q+1)
        answer.append(queue2.popleft())
        queue2.rotate(-q+1)
    else:
        queue.popleft()
        queue.rotate(-q)
        answer.append(queue2.popleft())
        queue2.rotate(-q)

print(answer)