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

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

2346번: 풍선 터뜨리기

 

 

핵심

시간초과 : Queue<Integer> q = new LinkedList<>()

해결방법 : ArrayDeque<int[]> list = new ArrayDeque<>();

 

→ ArrayDeque를 이용해서 {풍선번호, 종이값} 과 같은 형태로 큐의 요소 저장.

 

    

 

 

 

포인트

•  종이에 적힌 이동칸 수가 양수 또는 음수일 경우에 요소의 이동 

offerFirst(), offerLast() 메소드와

pollFirst(), pollLast() 메소드로

큐에서 앞의 요소를 뒤로,  뒤의 요소를 앞으로 옮길 수 있다. (양방향)

 

import java.util.*;

/*

1.ArrayDeque<int[]> list 를 이용해서 풍선번호, 종이값을 배열에 담는다.
2.list에서 요소를 꺼낸 뒤, 번호는 sb에 추가하고 종이값만큼 이동한다.
  양수 : 1 ~ 값 - 1 만큼 이동
  음수 : 값 ~ -1 만큼 이동
  
3.2번 작업을 반복하여 문자열 완성한 뒤 반환  

*/


public class Main{
    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        ArrayDeque<int[]> list = new ArrayDeque<>();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        for(int i = 1; i <= n; i++) {
            int[] arr = {i, sc.nextInt()};
            list.add(arr);
        }
        
        while(list.size() > 1) {
            int[] arr = list.pollFirst();
            sb.append(arr[0]).append(" ");
            
            int move = arr[1];
            if(move > 0) {
                for(int i = 1; i < move; i++) 
                    list.offerLast(list.pollFirst());
            }
            else {
                for(int i = move; i < 0; i++) 
                    list.offerFirst(list.pollLast());
            }
        }
        sb.append(list.poll()[0]);
        System.out.println(sb.toString());   
    }
}

 

 

 

 

기억하자 메소-드

✅  offerFirst(), offerLast() : 큐의 처음, 큐의 마지막에 원소 추가

✅  pollFirst(), pollLast() : 큐의 처음, 큐의 마지막 요소를 제거

 

✅   Map.getOrDefault(Object key, V defaultValue) 

key	찾을 키 값
defaultValue	키가 맵에 없을 경우 반환할 기본값
(예시) map.getOrDefault(c,0) + v	키 c가 맵에 없을경우 값을 0으로 설정하고 그게 아니라면 v를 더함