[백준] 2346번. 풍선 터뜨리기(JAVA)

문제

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

---

풀이(18분)

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

public class Main {
    // 원형임
    // 각 풍선 안 종이는 [-N,N]
    // 1번부터 터트리며 이동할 때는 이미 터진 풍선은 빼고 이동

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int count = n;
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        while(count > 0){
            int move = arr[idx];
            sb.append(idx+1).append(" ");
            count--;
            arr[idx] = 0;

            if(count == 0) break; // 마지막 풍선이면 끝

            while(move > 0){
                idx += 1;
                idx %= n; // 원형
                if(arr[idx] != 0){
                    move--;
                }
            }
            while(move < 0){
                idx += n - 1;
                idx %= n;
                if(arr[idx] != 0){
                    move++;
                }
            }

        }

        System.out.println(sb);
    }

}

---

문제 풀이 전략

 

단순하게 원형에 대한 구조만 처리해 주면 어려움이 없는 문제였다.

 

1. idx가 n범위를 초과하는 경우를 대비하여 mod n을 통해 인덱스를 맞춰준다.

2. idx가 0미만이 되는 경우를 대비하여 += n - 1, mod n 연산을 통해 인덱스를 맞춰준다.

 

이 경우 인덱스에 대한 제한 없이 정확하게 문제를 해결할  수 있다.

 

다만, 시간이 18분 걸린 부분은 내부에서 조건을 변경해 준다면 원하는 종료조건이 아니기에 무한 루프가 돈다는 것이었다.

if(count == 0) break;를 넣지 않는다면 arr[idx] != 0 조건을 모두 통과하여 while(move) 부분에서 무한 루프가 발생하게 된다.