[백준] 2346. 풍선 터트리기 (Java) [Deque]

문제

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

2346번: 풍선 터뜨리기

 

사용한 알고리즘

덱(Deque)

 

 

풀이

풍선이 양수, 음수일 때를 조건문으로 정해주고 Deque를 통해 방향 이동을 해주면 되는 문제였다.

종이가 양수 일 경우 앞 풍선을 뒤쪽으로 보내고,

종이가 음수 일 경우 뒤 풍선을 앞으로 보내주었다.

 

코드를 통해 확인해보자.

 

 

코드

package com.company;

import java.io.*;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Test_Deqeue {

    static int N;
    static ArrayDeque<Pair> dq;
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) {
        try {
            N = Integer.parseInt(bf.readLine());
            StringTokenizer st = new StringTokenizer(bf.readLine());
            dq = new ArrayDeque<>();
            for (int i = 1; i <= N; i++) {
                dq.add(new Pair(i, Integer.parseInt(st.nextToken())));
            }

            go();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    static void go() {
        StringBuilder sb = new StringBuilder();
        while (!dq.isEmpty()) {
            Pair item = dq.pollFirst();
            int idx = item.idx;
            int paper = item.paper;
            sb.append(idx+" ");

            if(dq.size()==0){ //풍선이 다 터졌으면 반복문 탈출
                break;
            }

            //풍선이동
            if (paper > 0) { //오른쪽 이동
                for (int i = 0; i < paper-1; i++) {
                    Pair tItem = dq.pollFirst();
                    dq.addLast(tItem);
                }
            } else { //왼쪽 이동
                for (int i = paper; i!=0; i++) {
                    Pair tItem = dq.pollLast();
                    dq.addFirst(tItem);
                }
            }
        }

        //출력
        try {
            bw.write(sb+"\n");
            bw.flush();
            bw.close();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }

    }

    static class Pair {
        int idx;
        int paper;

        public Pair(int idx, int paper) {
            this.idx = idx;
            this.paper = paper;
        }
    }
}

 

 

덱 사용법

https://soft.plusblog.co.kr/24

[Java(자바)] Deque(덱/데크) 자료구조

 

 

다른 사람 참고한 풀이

https://velog.io/@brince/%EB%B0%B1%EC%A4%80-2346%EB%B2%88-%EC%9E%90%EB%B0%94-%ED%92%80%EC%9D%B4