[JAVA]백준 2346번: 풍선 터뜨리기

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

2346번: 풍선 터뜨리기

 

1. 문제 설명

 

N개의 풍선이 있다.

풍선을 터뜨리면 풍선 안에 있는 -N ~ N 까지의 수가 적혀있는 종이를 얻을 수 있다.

그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다면, 풍선을 터뜨리는 순서를 구하는 문제이다.

 

2. 풀이

 

2가지 방법으로 풀었다.

 

1. Deque 사용

- 간단하게 풀 수 있다. 주의해야 될 점은 Deque를 정의할 때 LinkedList로 정의하게 되면 메모리 초과가 발생할 수 있다는 점이다.

- 순차적인 데이터 추가, 삭제에는 ArrayList를 사용하는 것이 더 효과적이다.

2. 배열 사용

- 간단하게 인덱스를 이용해서 풀 수 있다.

 

 

3. 코드

import java.io.*;
import java.security.Signature;
import java.text.DecimalFormat;
import java.util.*;


/*
	Deque 사용
 */
public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int num = Integer.parseInt(br.readLine());


        Deque<int[]> list = new ArrayDeque<>();
        StringTokenizer input = new StringTokenizer(br.readLine());

        sb.append("1 ");
        int move = Integer.parseInt(input.nextToken());

        for (int i = 2; i <= num ; i++) {
            list.add(new int[]{i, Integer.parseInt(input.nextToken())});
        }

        while (!list.isEmpty()) {
            if (move > 0) {

                for (int x = 1; x < move; x++) {
                    list.add(list.pollFirst());
                }

                int[] next = list.removeFirst();
                move = next[1];
                sb.append(next[0]).append(" ");
            } else {


                for (int x = move; x < -1; x++) {
                    list.addFirst(list.pollLast());
                }

                int[] next = list.removeLast();
                move = next[1];
                sb.append(next[0]).append(" ");
            }
        }

        System.out.println(sb);


    }




}

import java.io.*;
import java.security.Signature;
import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;


/*
	배열 사용
 */
public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int num = Integer.parseInt(br.readLine());

        int index = 0;

        LinkedList<int[]> list = new LinkedList<>();
        StringTokenizer input = new StringTokenizer(br.readLine());

        for (int x = 0; x < num; x++) {
            list.add(new int[]{x+1,Integer.parseInt(input.nextToken())});
        }

        while (list.size()!=1) {
            int move = list.get(index)[1];
            int size = list.size() - 1;

            sb.append(list.get(index)[0]).append(" ");

            list.remove(index);


			// 원소를 하나 삭제함으로 이미 한번 이동했다고 할 수 있다.
            if (move > 0) {
                move--;
            }

            index = (index + move) % size;

            if (index < 0) {
                index += size;
            }

        }

        sb.append(list.get(0)[0]);

        System.out.println(sb);

    }

}