[Java] 백준 2346 풍선 터뜨리기

2346 풍선 터뜨리기 문제 링크

문제분석

• 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있음
• i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있음
• 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있음
• 각 풍선 안에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 적힌 종이가 있음
• 이 풍선들을 다음과 같은 규칙으로 터뜨린다
  • 처음에는 1번 풍선을 터뜨림
  • 다음에는 풍선 안에 있는 종이를 꺼내 그 종이에 적혀있는 값만큼 이동 후 다음 풍선을 터뜨림
  • 양수가 적힌 경우에는 오른쪽으로, 음수가 적힌 경우 왼쪽으로 이동
  • 이미 터진 풍선은 빼고 이동함

제약 사항

• 종이에 0은 적혀있지 않음

입력 조건

• 첫째 줄 : 풍선의 개수 N(1 ≤ N ≤ 1,000)
• 둘째 줄 : 차례로 각 풍선 안의 종이에 적혀 있는 수

출력 조건

• 터진 풍선의 번호를 차례로 나열

#1

• index 체크 용으로 배열 하나 만들고 -> indexCheck
• 풍선을 터트리는 용으로 배열을 하나 만들어 -> nextArr
• nextArr에서 풍선을 터트리고 indexCheck에서 index를 체크해서 answer에 넣어
  
  
• check함수는 풍선에서 나온 정수대로 옮기면서 배열 범위를 벗어나는 경우를 체크해줘

import javax.swing.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int N = sc.nextInt();
        int[] indexCheck = new int[N];
        int[] answer = new int[N];
        ArrayList<Integer> nextArr = new ArrayList<>();
        int a;

        for(int i=0; i<N; i++) {
            a = sc.nextInt();
            indexCheck[i] = a;
            nextArr.add(a);
        }

        int index = 0;
        int remove = 0;
        for(int i=0; i<N-1; i++) {
            for(int C=0; C<indexCheck.length; C++) {
                if(nextArr.get(index) == indexCheck[C]) {
                    answer[i] = C+1;
                    indexCheck[C] = 0;
                    break;
                }
            }
            remove = index;
            index += nextArr.get(index)<0 ? nextArr.get(index) : nextArr.get(index)-1;
            nextArr.remove(remove);
            index = check(index, nextArr.size());
        }

        for(int C=0; C<indexCheck.length; C++) {
            if(nextArr.get(index) == indexCheck[C]) {
                answer[N-1] = C+1;
                indexCheck[C] = 0;
            }
        }

        for(int i=0; i<N-1; i++) {
            System.out.print(answer[i] + " ");
        }
        System.out.print(answer[N-1]);
    }
    static int check(int index, int nextArrL) {
        if(index >= nextArrL) return check(index-nextArrL, nextArrL);
        else if(-index >= nextArrL) return check(index+nextArrL, nextArrL);
        else if(index < 0) return index+nextArrL;
        return index;
    }
}

#2

• 덱을 이용해서 풀면 된대서 해봄

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        Deque<Integer>[] arr = new Deque[2];
        int[] answer = new int[N];

        // Deque 배열 초기화
        arr[0] = new ArrayDeque<>();
        arr[1] = new ArrayDeque<>();

        for(int i=0; i<N; i++) {
            arr[0].addLast(i+1);
            arr[1].addLast(sc.nextInt());
        }

        for(int i=0; i<N; i++) {
            answer[i] = arr[0].pollFirst();
            int index = arr[1].pollFirst();
            if(N-1 == i) continue;
            if(index > 0) {
                for(int j=1; j<index; j++) {
                    arr[0].addLast(arr[0].pollFirst());
                    arr[1].addLast(arr[1].pollFirst());
                }
            } else {
                for(int j=index; j<0; j++) {
                    arr[0].addFirst(arr[0].pollLast());
                    arr[1].addFirst(arr[1].pollLast());
                }
            }
        }

        for(int i=0; i<N-1; i++) {
            System.out.print(answer[i] + " ");
        }
        System.out.print(answer[N-1]);
    }
}

• 성공!

해결방안

Deque<Integer>[] arr = new Deque[2];
        int[] answer = new int[N];
        // Deque 배열 초기화
        arr[0] = new ArrayDeque<>();
        arr[1] = new ArrayDeque<>();

• 이렇게 하면 덱 배열에 각각 덱을 또 넣어준 것

// 입력된 원소와 인덱스를 저장할 덱(Deque) 생성
        Deque<int[]> list = new ArrayDeque<>();

• 덱 자료형을 이렇게 만드는 게 내 의도였음
• 아래 코드처럼 해주면 나처럼 배열[0],[1]을 각각 옮기지 않고 덱 원소를 옮겨주는 걸로 해결 가능함
• list.offerLast(list.pollFirst()); 이런 식으로?