[P&B] #108 BAEKJOON 2346

백준 2346번 풍선 터뜨리기 JAVA

문제 설명

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

 

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

 

나의 문제 풀이 코드

public class bj2346 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        List<Balloon> balloons = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            balloons.add(new Balloon(i, Integer.parseInt(st.nextToken())));
        }

        StringBuilder sb = new StringBuilder();
        int currentIndex = 0;

        while (!balloons.isEmpty()) {
            Balloon balloon = balloons.remove(currentIndex);
            sb.append(balloon.index).append(" ");

            int move = balloon.value;
            int size = balloons.size();

            if (size == 0) break;

            if (move > 0) {
                currentIndex = (currentIndex + move - 1) % size;
            } else {
                currentIndex = (currentIndex + move) % size;
                if (currentIndex < 0) currentIndex += size;
            }
        }

        bw.write(sb.toString());
        bw.close();
    }

    static class Balloon {
        int index;
        int value;

        public Balloon(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }
}

 

문제 풀이 코멘트

첫번째로 푼 코드는 아래와 같습니다. 이 코드는 테스트는 모두 실행되었으나 메모리 초과가 되어 실패했습니다. 덱(Deque)를 사용하여 풍선을 저장하고 이동하는 방식으로 구현되어 있습니다. 덱의 addLast()와 addFirst()를 사용하여 오른쪽으로 이동과 왼쪽으로 이동을 처리합니다. 그리고 각 풍선의 순서를 나타내는 num 리스트를 사용하여 풍선이 터진 순서를 기록하고 출력할 때 사용합니다.

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

public class bj2346 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Deque<Integer> balloon = new LinkedList<>();
        List<String> num = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            num.add(st.nextToken());
            balloon.add(Integer.parseInt(num.get(i)));
        }

        StringBuilder sb = new StringBuilder();
        int count = 0;
        while (count < N){
            int index = balloon.peekFirst();
            sb.append(balloon.pop()+" ");
            count++;

            if (index>0) {
                for (int i = 0; i < index-1; i++) {
                    balloon.addLast(balloon.pollFirst());
                }
            } else {
                for (int i = 0; i < Math.abs(index); i++) {
                    balloon.addFirst(balloon.pollLast());
                }
            }
        }

        for (String str :
                sb.toString().split(" ")) {
            bw.write(String.valueOf(num.indexOf(str)+1)+" ");
        }
        bw.close();
    }
}

하지만 이 코드는 입력받는 N이 매우 큰 경우, 첫 번째 코드에서는 데크(Deque)와 리스트(List)에 모든 풍선과 그 순서를 저장하므로 메모리 사용량이 크게 증가할 수 있습니다. 대용량 입력을 처리하기 위해 더 많은 메모리가 필요하면 메모리 초과가 발생할 수 있습니다.

 

성공 코드 설명

테스트에 통과한 문제 풀이 코드는 Balloon 객체를 사용하여 풍선의 인덱스와 값을 함께 저장합니다. 풍선 리스트를 사용하여 풍선의 인덱스와 값을 객체로 저장하고, 나중에 이를 사용하여 정렬 및 처리합니다. 객체를 활용했기 때문에 코드의 가독성과 유지보수성이 더 높습니다. 이동 방식은 나머지 연산을 사용하여 오른쪽으로 이동할 때와 왼쪽으로 이동할 때를 구분합니다.

 우선, 입력을 받고 생성된 풍선 객체(Balloon)를 타입으로 하는 리스트(balloons)에 인덱스(풍선 번호)와 풍선의 값을 저장합니다.
 초기 인덱스 currentIndex는 0으로 설정합니다. 그리고 현재 인덱스에 있는 풍선을 터뜨리고 결과 문자열(sb)에 해당 풍선의 인덱스를 추가합니다. 풍선의 값을 move에 저장하고, 리스트의 크기를 size에 저장합니다. 이 과정을 만약 풍선이 모두 터질때까지 반복합니다.
 move 값이 양수인 경우, 오른쪽으로 이동해야 합니다.

 currentIndex에 move - 1을 더하고, 나머지 연산(% size)을 사용하여 리스트의 크기를 넘어가지 않도록 합니다. 이렇게 하면 오른쪽으로 move 칸만큼 이동하게 됩니다.
 move 값이 음수인 경우, 왼쪽으로 이동해야 합니다.
 currentIndex에 move를 더하고, 마찬가지로 나머지 연산(% size)을 사용하여 리스트의 크기를 넘어가지 않도록 합니다.
 그러나 만약 currentIndex가 음수가 되는 경우, 리스트의 끝에서부터 이동해야 합니다. 따라서 currentIndex가 음수인 경우, 리스트 크기 size를 더해주어서 음수를 양수로 변환합니다.
 이렇게하면 양수와 음수 모두에 대한 풍선 이동을 처리하고, 리스트의 크기를 넘어가지 않도록 보장합니다. 따라서 다음 풍선을 올바른 위치에서 터뜨릴 수 있습니다. 각 풍선이 주어진 조건에 따라 터지면, 결과적으로 터진 풍선의 순서를 출력할 수 있게됩니다. 이 코드는 객체 지향적인 접근 방식을 사용하여 코드의 가독성을 높이고 유지보수를 용이하게 만들뿐만 아니라 메모리를 더 효율적으로 사용합니다.