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

2346번: 풍선 터뜨리기 (acmicpc.net)

2346번: 풍선 터뜨리기

 

 

풀이 과정

 

- 풍선에는 음수와 양수 모두 존재하기 때문에 움직임의 방향이 두가지 

 

- 양수가 나온다면 해당 숫자 만큼 움직이면서 앞에 있는 값을 pollFirst한 후 뒤로 addLast()

- 음수가 나온다면 반대방향으로 뒤에 있는 풍선들을 pollLast한 후 앞으로 addFirst()

 

- 풍선 번호와 안에 적힌 종이를 HashMap을 통해 처리

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.HashMap;

public class Main {
	
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        Deque<Integer> deque = new ArrayDeque<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        
        int n = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++)
        {
        	int paper = Integer.parseInt(st.nextToken());
        	map.put(i, paper);
        	deque.add(i); //덱에 풍선 번호 저장 
        }
        
        
        while (!deque.isEmpty()) {
            int cur = deque.pollFirst();
            Integer paper = map.get(cur);

            bw.write(cur + " ");

            if (paper != null) { 
                if (paper > 0) {
                    while (--paper > 0) {
                        int temp1 = deque.pollFirst();
                        deque.addLast(temp1);
                    }
                } else {
                    while (++paper < 0) {
                        int temp2 = deque.pollLast();
                        deque.addFirst(temp2);
                    }
                }
            }
        }

        
        bw.flush();
        bw.close();
    }
 }

 

 

 

- 메모리 초과 뜸....

 

- 구글링 해보니 deque에 배열형식으로 담아서 처리하는 것을 확인 

 

참고 블로그 

 

[백준_2346번] 풍선 터뜨리기 (tistory.com)

[백준_2346번] 풍선 터뜨리기

 

 

정답 

 

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

class Balloon {
	int idx; //풍선 번호
	int paper; //적혀 있는 값
	
	public Balloon(int idx, int paper)
	{
		this.idx = idx;
		this.paper = paper;
	}
}

public class Main {
	
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        Deque<Balloon> deque = new ArrayDeque<>();
         
        int n = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++)
        {
        	int paper = Integer.parseInt(st.nextToken());
        	deque.add(new Balloon(i,paper)); //덱에 풍선 번호 저장 
        }
        
        
        while (!deque.isEmpty()) {
            bw.write(deque.getFirst().idx+" ");
            
            int cur = deque.pollFirst().paper;
            
            if(deque.isEmpty())
            	break;
            
            if(cur>0) {
            	for(int i=0; i<cur-1; i++)
            	{
            		deque.addLast(deque.pollFirst());
            	}
            }
            else
            {
            	for(int i=0; i<Math.abs(cur); i++)
            	{
            		deque.addFirst(deque.pollLast());
            	}
            }
        }

        
        bw.flush();
        bw.close();
    }
 }