문제 url:
풍선 터트리기
문제:
🤔 문제 알아보기
해당 문제는 그림을 설명해보겠다.
이런 형태가 될 수 있다. 여기서 문제에 다음과 같은 조건이 있기 때문에 해당 그림이 가능한 것이다.
풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다.
이를 풀기 위해서 우리는 Deque을 이용할 수 있다.
먼저, 움직이는 수가 양수라면, 왼 -> 오 이동하는데,
첫 번째 경우에서 3만큼 움직일 때, 우리는 2와 1 을 지나처야 한다.
지나가는 값을 빼서 -1뒤로 추가해준다면! 원형처럼 사용할 수 있다.
반대로, 움직이는 수가 음수라면 왼 <- 오 이동하는데,
그러면 두 번째 경우에서 -3만큼 움직일 때, 우리는 1과 2를 거쳐서 -1로 와야한다.(원형이니깐, 돌고 돌면 -1로 오게된다.) 그러면 거쳤던 값을 빼서 또 뒤로 넣어주면 원형의 형태가 되지 않겠는가?
이를 그림으로 다시 표현해보자면
이런 그림이 될 것이다.
이는 코드와 함께 보면 이해가 더 될 것 같다.
하지만, 우리는 tc에서 3, 2, 1, -3, -1 값이 순서대로 몇 번째에서 등장하는지를 묻고 있다.
이를 계산하기 위해서는 deque에 배열형태로 넣어 HashMap처럼 tc에 적힌 값의 인덱스 번호를 보존하고자 한다.
여기서 주의! 자바에서 메모리 초과가 뜨는 분이 계실거다.
그 이유는 Deque를 ArrayDeque로 생성한 것이 아닌, LinkedList로 생성했기 때문이다.
아래는 해당 이유에 대한 chat-GPT의 답변이다.
이제 코드와 함께 알아보자
🐱👤 실제 코드
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));
StringBuilder sbd = new StringBuilder();
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Deque<int[]> deque = new ArrayDeque<>();
int[] arr = new int[N];
int idx = 0;
// 배열에 값을 넣기 위한 반복문
while(st.hasMoreTokens()) {
int num = Integer.parseInt(st.nextToken());
arr[idx++] = num;
}
// 1부터 시작하는 이유는 첫번쨰 인덱스 값을 터트리고 시작하기 때문에
// 그 다음 인덱스인 1부터 시작하는 것
// i+1를 한 이유는 순서가 1-based position이기 때문
for(int i = 1; i < N; i++) {
deque.offer(new int[]{arr[i], i+1 }); // {풍선 값, 인덱스 위치}
}
sbd.append(1).append(" ");
// 첫 번째는 반드시 터트린다고 했으니, 첫 번째 배열에 있는 값을 넣어준다.
int move = arr[0];
for(int i = 1; i < N; i++) {
/*
* move가 양수라면
*/
if(move > 0) {
for(int j = 1; j < move; j++) {
deque.offer(deque.poll());
}
int[] move_arr = deque.poll();
move = move_arr[0];
sbd.append(move_arr[1]).append(" ");
}
/*
* move가 음수라면
*/
else {
for(int j = 1; j <-move; j++) {
deque.offerFirst(deque.pollLast());
}
int[] move_arr = deque.pollLast();
move = move_arr[0];
sbd.append(move_arr[1]).append(" ");
}
}
System.out.println(sbd);
}
}
🤢 트러블 슈팅
처음에는 메모리 초과가 뜨면서, 이전 코드에서 메모리가 높은 자료구조를 낮은
(ArrayLIst -> array 로 변경)하면서 메모리를 줄여봤지만, 계속 초과를 했다.
그래서 블로그를 보니.. LinkedList를 사용하면 안되고 ArrayDeque를 사용해야 했다.
그런 다음, 문제를 풀어보니 아뿔싸! 이번엔 틀린 것이다.
틀린 이유를 찾아보니, 필자는 tc 3, 2, 1, -3, -1를 배열에 넣고 indexOf를 통해 인덱스 값을 찾았는데 반례로 2, 2, 2, 2 를 넣으니 틀렸다고 나온 것이다.
그후.. 블로그를 참고하면서 Deque안에 배열을 넣을 수 있다는 사실과 함께 해당 배열로 HashMap과 유사하게 값을 보관할 수 있는 것을 배울 수 있었다.
아래는 이전 코드이다. 이렇게 반례를 잘 넣어서 조건에 맞게 문제를 풀 수 있도록 연습해야겠다.
import java.io.*;
import java.util.*;
public class Main {
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
arr = new int[N];
int idx = 0;
Deque<Integer> deque = new ArrayDeque<>();
while(st.hasMoreTokens()) {
int num = Integer.parseInt(st.nextToken());
arr[idx++] = num;
deque.offer(num);
}
int balloon = deque.poll();
System.out.print(indexOf(balloon)+1 + " ");
// sbd.append(arr.indexOf(balloon)+1).append(" ");
for(int i = 0; i < N-1; i++) {
// balloon이 0보다 크다면, 오른쪽으로 이동
// balloon이 터지는 시점만큼 움직이는데, balloon-1만큼 움직임.
if(balloon > 0) {
for(int j = 0; j < balloon-1; j++) {
deque.offer(deque.poll());
}
// balloon(풍선이 터지는 시점)
balloon = deque.poll();
System.out.print(indexOf(balloon)+1 + " ");
// sbd.append(arr.indexOf(balloon)+1).append(" ");
}
/*
* balloon이 0보다 작으면, 왼쪽으로 이동
* balloon이 터지는 시점만큼 움직이는데, balloon-1만큼 움직임.
*/
else {
for(int j = 0; j < Math.abs(balloon)-1; j++) {
deque.offerFirst(deque.pollLast());
}
// 풍선이 터지는 시점
balloon = deque.pollLast();
System.out.print(indexOf(balloon)+1 + " ");
// sbd.append(arr.indexOf(balloon)+1).append(" ");
}
}
// System.out.println(sbd);
}
static int indexOf(int balloon) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == balloon) {
balloon = i;
break;
}
}
return balloon;
}
}
💜 참고자료
