[백준]2346: 풍선 터뜨리기 , 덱 개념

 

아주 머리가 지끈지끈 거리는 문제였다.

덱에 대한 개념과 이 문제에 대한 풀이를 진행하도록 하겠새우 가봅새우.

---

Deque

 

덱은 말그대로 카드 덱을 생각하면 된다.

맨 위에서도 접근이 가능하고 맨 아랫장을 빼고 넣을수도있다.

스택과 큐가 합쳐진 최종보스새우 느낌이다.

이때문에 사용되는 매소드도 완즈히 고도로 발달된 느낌이다.

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

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

특이한 메소드는

offerFirst, pollLast, peekLast 등등 기존 큐에서는 볼 수 없던 앞 뒤로 자유자재로 컨트롤 할 수 있다는 장점이있다.

 

주의 할 점은 , ArratDeque로 선언 하는 방법이 있고, LinkedList로 선언 하는 방법이 있는데,

https://velog.io/@becooq81/JAVA-ArrayDeque%EB%A5%BC-%EC%82%AC%EC%9A%A9%ED%95%B4%EB%B3%B4%EC%9E%90

[JAVA] ArrayDeque를 사용해보자

아직은 둘의 차이는 모르겠다. 다만 , ArrayDeque가 메모리 효율이 더 좋고 Deque를 쓸때는 아직까지는 이걸 사영해야겠다.

---

정답 코드

package que;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q5 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Deque<Integer> deque = new ArrayDeque<>();
        Deque<Integer> dequeNum = new ArrayDeque<>();
        int[] arr = new int[N];
        for (int i = 1; i <= N; i++) {
            deque.offer(i);
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            dequeNum.offer(Integer.parseInt(st.nextToken()));
        }
        arr[0] = deque.poll();
        int a = dequeNum.poll();
        int j = 1;
        while (j < N) {
            if (a > 0) {
                for (int i = 0; i < a; i++) {
                    deque.offer(deque.poll());
                    dequeNum.offer(dequeNum.poll());
                }
                arr[j] = deque.pollLast();
                a = dequeNum.pollLast();
            } else {
                for (int i = 0; i < a * -1; i++) {
                    deque.offerFirst(deque.pollLast());
                    dequeNum.offerFirst(dequeNum.pollLast());
                }
                arr[j] = deque.poll();
                a = dequeNum.poll();
            }
            j++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i : arr) {
            sb.append(i).append(" ");
        }
        System.out.println(sb);

    }
}

 

 

 

링크드리스트를 사용하면 메모리초과가 엄청나게 난다.

자, 코드 설명을 해보자면,

우선, 1은 무조건 맨 처음 제거가 된다.

 

1. 따라서 파이널에다가 1을 넣어주기 위해서 poll을 해준다.

 

2. j변수를 선언해주는데, 이건 몇개를 파이널에 옮겨줬느냐를 따져주는거므로, while의 조건식이 될수있다.

 

자, 이제 중요한것 나갑니다. 필자는 숫자카드 위에 서있다고 가정하고,

카드가 배열된 방식과 필자가 보는 방향은 시계방향(오른쪽)으로 절대 변하지 않는다.

양수방향과 음수방향으로 움직이는것은 그저 앞과 뒤로 움직이는것으로 정의하겠다.

중요 !!!!!!!!!!!! 필자는 항상 맨 앞 또는 맨뒤에 위치해야한다. 그래야지 poll을 할 수 있따.

3-1 . 이제 a에서 deqNum을 받아온다---->

a가 양수면?---->

1. 본인이 서있던 카드에서 양수방향으로 움직인다.

2. 원래 본인이 서있었던 카드는 본인의 뒤에 있게 된다.

3. 따라서 서있었던 카드를 poll해서 맨 뒤에 offer해주면 된다.

 

4. deqNum도 숫자카드를 따라서 똑같이 수행한다.

5. a번 수행하게 되면,

a번째에 있는 값이 맨 뒤에 있게된다. 그 값을  poll해주려면 pollLast를 해줘야한다~!

 

왜 poll을 여기서 해주냐면 맨 첨에 1은 이미 저장을 시켜놨고, 반복되는 알고리즘이

 

(1)반복횟수만큼 옮겨가기

(2)목표위치 도착했으니 제거해주기, 제거했던 숫자카드 밑의 움직이는 수 저장

 

이렇게 반복하면 된다.

 

3-2. 만약 a가 음수라면,

본인이 서있던 카드에서 음수방향으로 움직이면(뒤로 간다),

서있었던 카드는 본인의 앞에 서있게 된다.

따라서 앞에 있는 카드를 맨 뒤로 보내주는 작업을 가져주면 된다.

pollLast한 것을 offerFirst!

그렇게 하면은 원하는 횟수만큼 반복하고 난 후,

본인이 원하는 수가 덱의 맨 앞에 있을것이다.

따라서 그냥 poll해서 덱 파이널에 저장.

---

이렇게 해서 풀어보았다.

푼 직후라서 내 머릿속에 있는것을 최대한 글로 표현해봤새우~

두서없이 정리된 것이지만, 이 문제를 풀때 도움이 되길 바라고,

제일 중요한것은 덱을 선언할때 ArrayDeque로 선언해야한다는것!!!!!!!!!!!!

나처럼 메모리 초과로 고통받지 않길 원한다.

이상입니새우~