백준 2346번: 풍선 터뜨리기 (JAVA) <DEQUE>

 

 문제 해석

 

원형으로 1번부터 N번까지의 풍선이 놓여있다. 풍선 안에는 종이가 들어있고 종이에는 -N이상 N이하의 정수가 적혀있다.

풍선을 터뜨리고 종이에 적힌 값만큼 이동하는 과정을 반복한다.

 

알고리즘

 

원형 큐를 만들고 종이에 음수가 적힌 경우를 적절히 처리하면 될 것 같아 큐를 이용해 원형 구조를 구현하였는데 메모리 초과가 떴다. 이후 이것저것 바꿔보다 덱을 사용해야함을 알게 되었다.

큐는 입력부분과 출력부분이 각각 존재하기에 이용시 따로 본인이 작성을 안하여도 front와 rear에 대해 메모리를 추가로 사용하여 메모리 초과가 발생되는 것 같다.

덱을 이용하여 입력부분과 출력부분을 자유롭게 사용하고 메모리 사용률을 감소시켰다.

또한 종이에 적힌 수가 아닌 터진 풍선의 번호를 출력해야 한다.

따라서 메모리 사용을 최소화하기 위해 클래스를 활용해 덱에 인자를 두가지 넘겨주었다.

 

코드