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

풀이 방법

예전에 한 번 풀어본 문제이지만, 인간의 기억력은 역시나… 오래 지속되지 않는다는 걸 알면서도 똑같은 실수를 반복했습니다…ㅜ 그래서 저는 다시 풀어보았습니다. 다행스럽게도 풀어본 경험이 있어서인지 문제를 보고 어떻게 접근해야 하는지 생각할 수 있었습니다.

  1. Class 만들기
    풍선의 순서와 풍선에 적혀있는 값을 가지고 있는 Class를 만들어서 사용하면 됩니다.

  2. List 사용
    이 문제를 풀기 위해서 위에서 만든 Class를 타입으로 갖는 객체 배열을 사용할지 리스트를 사용할지 생각했습니다. 이 문제에서는 풍선을 터뜨릴 경우 삭제를 해줘야 하기 때문에 추가 및 삭제가 일어나도 빈 공간을 처리하지 않아도 되는 즉, 빈 공간이 자동으로 채워지는 List를 사용하였습니다.

  3. 터뜨릴 순서?
    풍선을 터뜨릴 순서를 결정하기 위해서는 풍선에 적혀있는 값을 가지고 결정해야 합니다. 풍선에 적혀있는 값이 양수이면 오른쪽으로 돌고, 음수이면 왼쪽으로 돌아서 풍선을 터뜨리면 됩니다. 문제에서 풍선은 원형처럼 1번의 왼쪽에는 N번 풍선이, N번의 오른쪽에는 1번 풍선이 있다고 하였으므로 참고해서 돌고 터뜨리면 됩니다.

주의할 점은 처음에 터뜨릴 풍선은 1번 풍선인데, 이 풍선을 터뜨리고 나면 1번 풍선이 사라지면서 2번째 풍선이 1번 풍선의 인덱스를 가지게 됩니다. 그러므로 첫번째 풍선을 이미 터뜨리고 나서 풍선에 적힌 값에 따라서 다음에 터뜨릴 풍선을 결정할 때, 풍선에 적혀있는 값이 양수라면 (그 값 - 1) 만큼만 계산하면 됩니다. 왜냐하면 리스트에서 풍선이 삭제됨에 따라서 이미 한칸을 이동했기 때문입니다. (쉽게 말하면 풍선이 하나 터지면서 다른 풍선의 인덱스들이 터진 풍선 이후 부터 즉, 오른쪽부터 0부터 재할당되기 때문입니다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.StringTokenizer;

public class BOJ2346 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(bf.readLine()); // 테스트 케이스

        ArrayList<Ballons> ballons = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        for(int i=0;i<test_case;i++){
            int value = Integer.parseInt(st.nextToken());
            ballons.add(new Ballons(i+1, value));
        }

        String str = process(ballons, test_case);
        System.out.println(str);

    }
    public static String process(ArrayList<Ballons> ballon_list, int num){

        int kill=0; // 터뜨릴 풍선의 인덱스
        int value=0; // 터뜨릴 풍선의 값
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<num;i++){
            // value 즉, 풍선에 적혀있는 값이 양수인지 음수인지에 따라
            // 오른쪽 혹은 왼쪽으로 이동하기 위해 검사
            if(value>0){
                for(int k=0;k<value-1;k++){
                    ++kill;
                    if(kill>=ballon_list.size()){
                        kill=0;
                    }
                }
            }else if(value<0){
                value = Math.abs(value); // 절대값 변환
                for(int j=0;j<value;j++){
                    --kill;
                    if (kill<0){
                        kill = ballon_list.size()-1;
                    }
                }

            }


            /*FIXME
            * 처음에는 0번째 즉, 첫 번째 풍선을 터뜨려야 하기 때문에
            * 이렇게 터뜨릴 풍선을 정하고
            * 그 풍선의 값(value)[즉, 적혀있는 값!]를 알아낸다.
            * 왜냐하면, 다음 풍선을 터뜨리기 위해 얼만큼 이동할지 알기 위해서
            * */
            Ballons ballon = ballon_list.get(kill);
            System.out.println("삭제가 될 풍선 : "+ballon.valueNumber+", "+(ballon.orderNumber)+", "+kill);
            value = ballon.valueNumber;

            sb.append(ballon.orderNumber+" ");
            ballon_list.remove(kill);
            if(kill == ballon_list.size()){
                System.out.println("몇번?");
                kill = 0;
            }
        }
        return sb.toString();
    }
}
class Ballons{
    int orderNumber; // 풍선의 순서
    int valueNumber; // 풍선 안에 적힌 값

    public Ballons(int orderNumber, int valueNumber){
        this.orderNumber = orderNumber;
        this.valueNumber = valueNumber;
    }
}