[자바] 백준 2346번 풍선 터뜨리기

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

 

[문제 이해]

요세푸스랑 비슷해서 금방 풀 줄 알았는데 티어가 차이나는 이유가 있었구나,, 일단 인덱스 값을 저장해서 이를 출력해야되는 것이 가장 큰 차이점이었고, -(마이너스)값이 있기 때문에 값을 어떻게 배치해야하는가도 중요하게 생각해봐야할 부분 중 하나였다.

 

[문제 풀이]

값이 양수면 원래 값-1만큼 반복하면서 앞에서 원소를 빼고 뒤에 삽입하면 됐었고, 값이 음수면 원래 값만큼 반복하면서 뒤에서 앞으로 값을 삽입하면 되는 문제였다.

처음에는 LinkedList로 선언해서 메모리 초과 파티를 겪은 이후, 이를 수정했더니 이번에는 NullPointer 오류가 났다. 간단한 예제 (123)으로 테스트 해보니 마지막 값일 경우, NullPointer 오류가 나는 경우도 있음을 알게 되었다. 다시 느끼는 테스트 케이스와 예외 처리의 중요성.. 아무튼 deque에서 가장 마지막 값만 남았을 때에는 즉, poll을 통해 마지막 원소를 꺼낸 이후에는 size가 0이므로 더이상 작업을 처리하지 않도록 break로 for문에서 탈출할 수 있게 코드를 수정함으로써 .. 코드를 완성할 수 있었다..! 아직도 실버 3이 어렵다니😂

아 그리고 deque안에 원소를 list로 저장할 수 있는 걸 처음 알았는데 찾아보니까 다른 방법으로도 할 수 있었지만 나는 그냥 임시 배열 하나를 만들어서 해당 배열 각각의 원소에 값을 넣고 이를 저장하는 방식을 사용했다. 이것보다 간단한 방법이 있었는데 new int[] 로 배열 생성하고 진짜 배열을 밖에서 생성하듯이 {} 안에 넣고 싶은 값을 넣어주면 되었다.

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));

        Deque<int[]> deque = new ArrayDeque<>();
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            int[] tmp = new int[2];
            tmp[0] = i+1;
            tmp[1] = Integer.parseInt(st.nextToken());
            deque.offerLast(tmp);
        }

        br.close();

        for(int i = 0; i < N; i++){
            int tmp = deque.peekFirst()[1];
            arr[i] = deque.pollFirst()[0];
            if(deque.size() == 0){
                break;
            }
            if(tmp < 0){
                for(int j = 0; j < -tmp; j++){
                    deque.offerFirst(deque.pollLast());
                }
            }
            else{
                for(int j = 0; j < tmp-1; j++) {
                    deque.offerLast(deque.pollFirst());
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i < N; i++){
            bw.write(String.valueOf(arr[i]) + " ");
        }
        bw.flush();
        bw.close();
    }
}