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

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

2346번: 풍선 터뜨리기

 

접근 방식)

풍선이 원형으로 놓여있고, 오른쪽 왼쪽으로 이동 → 앞/뒤로 꺼내서 넣어줘야 함 → Deque 사용

★ [메모리 초과] Deque 사용할 때 LinkedList로 정의해서 메모리 초과 발생했었다. (ArrayDeque<>() 로 정의)

 

1) 풍선 객체 사용 (순서와 종이에 적인 번호 속성 가짐), 앞뒤로 꺼낼 Deque 사용

1번째 풍선은 터뜨린다고 하니까, 그냥 터뜨림

2) queue가 빌 때까지 반복

  2-1) 종이에 적힌 번호가 양수라면, 

  반복문돌면서 큐의 앞에서 꺼내, 뒤에 넣고

  ★맨 앞에 있는 풍선 꺼냄

2-2) 음수라면,

  반복문돌면서 큐의 뒤에서 꺼내, 앞으로 넣고

  ★맨 뒤에 있는 풍선 꺼냄

 

package tony_git.data_structure;

import java.util.*;
public class B_2346 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Deque<Balloon> que = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++)
            que.add(new Balloon(i, sc.nextInt()));

        // 첫번째 풍선 터뜨림
        Balloon balloon = que.poll();
        int paperNum = balloon.paper;
        sb.append(balloon.order + 1).append(' ');

        while(!que.isEmpty()) {
            if (paperNum > 0) {
                for (int i = 1; i < paperNum; i++)
                    que.addLast(que.pollFirst());
                balloon = que.pollFirst();  //--★ 풍선 앞에서 꺼냄
            } else {
                for (int i = paperNum; i < -1; i++)
                    que.addFirst(que.pollLast());
                balloon = que.pollLast();   //--★ 풍선 뒤에서 꺼냄
            }
            paperNum = balloon.paper;
            sb.append(balloon.order + 1).append(' ');
        }
        System.out.println(sb);
    }

    static class Balloon {
        int order;
        int paper;

        public Balloon(int order, int paper) {
            this.order = order;
            this.paper = paper;
        }
    }
}

 

 

+) 23.09.22 추가

• BufferedReader 사용, 터뜨릴 풍선을 Deque 앞뒤에서 뺄 필요 없이, 앞에서만 빼도록 풀이

package tony_git.data_structure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.util.StringTokenizer;

public class B_2346_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Deque<Balloon> deque = new ArrayDeque<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            deque.add(new Balloon(i, Integer.parseInt(st.nextToken())));
        }

        StringBuilder sb = new StringBuilder();
        Balloon now = deque.removeFirst();
        sb.append(now.order).append(' ');

        while (!deque.isEmpty()) {
            int paperNum = now.paper;
            if (paperNum > 0) {
                for (int i = 1; i < paperNum; i++)
                    deque.addLast(deque.removeFirst());
            } else {
                for (int i = paperNum; i < 0; i++)
                    deque.addFirst(deque.removeLast());
            }
            now = deque.removeFirst();
            sb.append(now.order).append(' ');
        }
        System.out.println(sb);
    }
}

class Balloon {
    int order;
    int paper;

    public Balloon(int order, int paper) {
        this.order = order;
        this.paper = paper;
    }
}