[BOJ] 백준 2346 풍선 터뜨리기(Swift)

문제

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

풀이

오른쪽으로 이동하는 것 (양수)인 경우에는
array.append(array.removeFirst()) 를 통해 맨 앞으로 이동시킬 수 있다.
주의할 점으로는 적힌 숫자보다 -1 만큼 이동을 시켜주어야 한다.

예를 들어 다음과 같은 배열이 있을 때를 생각해보자.
array = [2, -1, 1]
가장 앞에 있는 2가 터지고 2만큼 뒤에있는 1이 터져야 할 상황이다.

2가 터졌기 때문에 index가 자연스럽게 1이 줄어들게 된다.
[-1, 1]

array.append(array.removeFirst()) 수행 시 다음과 같다.
[1, -1]

한 번만 수행해도, 1이 가장 앞에 위치하는 것을 확인할 수 있다.

왼쪽으로 이동하는 방식은 (음수) 다음과 같이 정의할 수 있다.
array.insert(array.removeLast(), at: 0)

가장 마지막의 원소를 가장 앞으로 옮겨주는 작업을 통해 왼쪽으로 옮겨줄 수 있다.

array = [-2, 1, -1]
가장 앞에있는 -2가 터지고 그 다음으로는 왼쪽으로 2만큼 이동시켜주어야 한다.

-2가 터지면 다음과 같다.
array = [1, -1]

array.insert(array.removeLast(), at: 0) 수행 시 다음과 같다.
array = [-1, 1]

한 번 더 수행 시, array = [1, -1] 이 된다.

이렇게 내가 원하는 동작을 수행할 수 있다.

Swift에서는 removeFirst() 메서드는 $O(n)$의 시간복잡도이다.
가장 앞에있는 원소를 삭제하고 그 이외의 원소를 앞으로 옮겨주는 작업이 있어야 하기 때문이다.
Deque 자료구조에서는 pop push 연산이 $O(1)$ 이여서 구현한 코드는 덱을 완벽히 구현한 코드는 아니다.

블로그에 $O(1)$로 Deque을 구현해둔 내용이 있어 이를 참고해도 좋고, 이 문제는 n이 작아서 $O(n)$으로 풀어도 풀리는 문제였다.

소스코드

• $O(n)$으로 플이한 방식
• $O(1)$으로 플이한 방식

후기

사실 이 문제는 deque을 안쓰고, 인덱스를 이동시켜서도 풀 수 있는 문제이다.
다만, 분류가 deque으로 되어있으니 deque을 활용해서 풀어보는 것도 좋은 것 같다.