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

🔺 문제

2346번: 풍선 터뜨리기

 

 

🧩  해결 아이디어

• 덱

- 덱 맨 앞에 있는 풍선 번호를 저장한다.

- 맨 앞 풍선을 꺼내고, 적힌 값을 변수 next로 갖는다.

└ 꺼내고 나서 남은 풍선이 없다면, while문을 종료한다.

 └ 양수가 적혀있을 때는, next 크기 -1까지 맨 앞의 원소를 뽑아 맨 뒤에 넣는다.

 └ 음수가 적혀있을 때는, 맨 뒤쪽 원소를 뽑아 맨 앞에 넣는다.

 

 

💥 유의사항

LinkedList로 작성하면 메모리 초과가 뜬다....

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
       Deque<Balloon> dq = new ArrayDedque<>();    // LinkedList로 하면 메모리 초과
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= N ; i++) {
            dq.add(new Balloon(i, Integer.parseInt(st.nextToken())));
        }
        
        while(!dq.isEmpty()) {
            // 덱 맨 앞에 있는 풍선 번호 저장하고, 꺼내서 적힌 값 저장
            sb.append(dq.getFirst().idx + " ");
            int next = dq.poll().val;
            
            // 남아있는 풍선 없으면 종료
            if(dq.isEmpty()) break;
            
            // 적힌 값이 양수인 경우
            if(next > 0) {
                for(int i = 0 ; i < next - 1 ; i++) {
                    dq.addLast(dq.pollFirst());
                }
            }
            // 적힌 값이 음수인 경우
            else {
                for(int i = 0 ; i < Math.abs(next) ; i++) {
                    dq.addFirst(dq.pollLast());
                }
            }
        }
        
        System.out.println(sb);
    }
}
 
class Balloon {
    int idx, val;
    
    public Balloon(int idx, int val) {
        this.idx = idx;
        this.val = val;
    }
}
 

 

 

---

🔺 다른 풀이들

- 배열 LinkedList 사용 (내가 하려고 했던 풀이ㅠ)

리스트 사이즈를 초장에 변수로 저장해두네....

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

---

💬 느낀 점

LinkedList 사용해서 풀려다가 음수 방향을 바꿀 때 처리가 제대로 안 되어서 고민하다가

다른 분 코드를 보고 작성하였다..

 

알고리즘아 도와줘...

 

1회독	2회독	3회독	4회독	5회독
V	240224

 

 

(+ 240224 2회독 : 15888KB, 152ms)

60분 소요,,,

LinkedList를 사용했다.

음수 방향 이동 시 인덱스 처리가 좀 헷갈렸다,,

시간 줄여야하는데,,

 

1. 양방향 리스트를 돌며 먼저 이동할 값을 저장하고, 터질 풍선을 출력하고, 풍선을 터뜨린다.

이 때 양방향 리스트가 비어있다면, 반복문을 종료한다.

len = q.get(pos).val;   // 이동할 값
sb.append(q.get(pos).idx + " ");   // 터지는 풍선
q.remove(pos);   // 풍선 터뜨리기

 

 

2. 이동거리가 양수라면  위치 pos를 pos = (pos + len - 1) % q.size() 위치로 이동시킨다.

이동거리가 음수라면, 아래처럼 위치를 조정하고 이동시키고 1번 단계를 다시 진행한다.

pos = (pos + len) % q.size();
if(pos < 0) pos += q.size();

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        StringBuilder sb = new StringBuilder();
        List<Node> q = new ArrayList<>();
        
        int N = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            q.add(new Node(i + 1, arr[i]));  // 인덱스, 값
        }
        
        int pos = 0;
        int len = 0;
        
        while(!q.isEmpty()) {
            len = q.get(pos).val; // 이동할 값
            sb.append(q.get(pos).idx + " "); // 터지는 풍선
           q.remove(pos); // 풍선 터뜨리기
            
            if(q.isEmpty()) break;
            
            if(len >= 0) { // 양수 방향 이동 시
                pos = (pos + len - 1) % q.size();
            }
            else {  // ⭐ 음수 방향 이동 시 ⭐
                pos = (pos + len) % q.size();
                
                if(pos < 0) pos += q.size();
            }
        }
        
        System.out.println(sb.toString());
    }
}
 
class Node {
    int idx, val;
    
    public Node(int idx, int val) {
        this.idx = idx;
        this.val = val;
    }
}
 

 

---

(참고)

✔ 풀이 참고

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