📌 문제

[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 ~ n번까지 순서대로 덱 d에 저장하고, 풍선의 번호와 종이에 적힌 숫자를 같이 가져가야하기 때문에 HashMap map을 선언하여 <번호, 숫자> 형식으로 저장하였다.

제일 처음으로 1번 풍선을 터뜨려야 하는데, 1번은 d의 출구 요소이므로 poll() 메서드를 사용하여 값을 꺼낸다. 이 때, map.get(poll())을 통해 1번 풍선에 적힌 숫자를 m에 저장한다. 이후, d 안의 요소 개수가 1개가 될 때까지 다음 작업을 반복 수행한다.

m > 0 : 숫자가 양수이면 오른쪽으로 m칸 이동해야 하는데, 이는 앞쪽에서 m번째 요소를 꺼내야 한다는 뜻이다. pollFirst() 메서드를 사용하여 앞쪽의 요소 m-1개를 꺼내 offerLast()를 통해 다시 뒤쪽으로 넣고, peekFirst()를 통해 m번째 요소를 출력한 후, pollFirst()를 통해 m번째 요소를 꺼내 m번째 풍선 안에 적힌 숫자를 다시 m에 저장하여 다음 반복을 수행한다.

m < 0 : 숫자가 음수이면 왼쪽으로 m칸 이동해야 하는데, 이는 뒤쪽에서 m번째 요소를 꺼내야 한다는 뜻이다. 전체적인 알고리즘은 m이 양수인 경우와 같은데, 값을 꺼내는 방향과 넣는 방향이 반대로 수행된다.

반복문이 종료되면 마지막 남은 요소를 출력하면서 종료한다.

아무래도 맵과 덱을 한 번에 사용해서 메모리를 많이 먹겠다 생각은 했는데 메모리 초과가 뜰 줄은,, 몰랐다,, 문제를 다시 보니 메모리 제한이 4MB였음 ㅎㅎ,,

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Deque<Integer> d = new LinkedList<>();
		Map<Integer, Integer> map = new HashMap<>();
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			int num = Integer.parseInt(st.nextToken());
			
			d.offer(i);
			map.put(i, num);
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(1).append(" "); // 1번 펑
		int m = map.get(d.poll()); // 이동할 값
		
		while(d.size() > 1) {
			if(m > 0) { // 오른쪽
				for(int i=0;i<m-1;i++) {
					d.offerLast(d.pollFirst());
				}
				
				sb.append(d.peekFirst()).append(" ");
				m = map.get(d.pollFirst());
				
			} else { // 왼쪽
				for(int i=0;i<(-1*m)-1;i++) {
					d.offerFirst(d.pollLast());
				}
				
				sb.append(d.peekLast()).append(" ");
				m = map.get(d.pollLast());
			}
		}
		sb.append(d.pollFirst()); // 마지막 펑
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

💾 아무래도 HashMap이 메모리를 많이 먹은 것 같아서 대신 배열을 사용하면 좀 낫지 않을까? 싶어서 map과 같은 역할을 수행하는 배열 arr[]를 선언해서 풀어봤는데 여전히 메모리 초과,,

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Deque<Integer> d = new LinkedList<>();
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n+1]; // map 대용
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			d.offer(i);
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(1).append(" "); // 1번 펑
		int m = arr[d.poll()]; // 풍선 안 숫자
		
		while(d.size() > 1) {
			if(m > 0) { // 오른쪽
				for(int i=0;i<m-1;i++) {
					d.offerLast(d.pollFirst());
				}
				
				sb.append(d.peekFirst()).append(" ");
				m = arr[d.pollFirst()];
				
			} else { // 왼쪽
				for(int i=0;i<(-1*m)-1;i++) {
					d.offerFirst(d.pollLast());
				}
				
				sb.append(d.peekLast()).append(" ");
				m = arr[d.pollLast()];
			}
		}
		sb.append(d.poll()); // 마지막 펑
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

✅ 도저히 모르겠어서 구글링 해보니 덱을 선언할 때 LinkedList를 사용하는 것보다 ArrayDeque를 사용하는 것이 노드에 대한 참조를 유지할 필요가 없어 메모리를 더 적게 사용한다고 한다! 나는 지금까지 큐나 덱을 선언 할 때 무조건 LinkedList를 사용했었는데, 다른 구현체를 사용할 수 있다는 것을 오늘 처음 알게 됐다,,

그리고 풍선 번호와 숫자를 같이 가져가는 방법에 대해도 다양한 풀이가 존재했는데, 맵이나 배열 대신 두 변수를 저장할 수 있는 클래스를 생성하여 푸는 방법이 있어서 ArrayDeque + 클래스 방식으로 풀어봤다. 클래스 또한 맵, 배열과 같은 역할을 하므로 전체적인 알고리즘은 위 두 코드와 같다!

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Deque<Balloon> d = new ArrayDeque<>();
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			d.offer(new Balloon(i, Integer.parseInt(st.nextToken())));
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(1).append(" "); // 1번 펑
		int m = d.poll().num; // 풍선 안 숫자
		
		while(d.size() > 1) {
			if(m > 0) { // 오른쪽
				for(int i=0;i<m-1;i++) {
					d.offerLast(d.pollFirst());
				}
				
				sb.append(d.peekFirst().idx).append(" ");
				m = d.pollFirst().num;
				
			} else { // 왼쪽
				for(int i=0;i<(-1*m)-1;i++) {
					d.offerFirst(d.pollLast());
				}
				
				sb.append(d.peekLast().idx).append(" ");
				m = d.pollLast().num;
			}
		}
		sb.append(d.poll().idx); // 마지막 펑
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

class Balloon { // 클래스 생성
	int idx; // 풍선 번호
	int num; // 풍선에 적힌 숫자
	
	public Balloon(int idx, int num) {
		super();
		this.idx = idx;
		this.num = num;
	}
}