[코테/알고리즘] Java - Deque를 이용한 알고리즘 풀이

Deque란? 

양쪽 끝에서 삭제와 삽입이 전부 가능하다. 

스택과 큐를 덱의 특수한 예시라고 생각할 수 있다.

 

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 앞/뒤의 원소 확인이 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

 

배열과 연결리스트 둘다 구현할 수 있지만, 배열을 이용하는 방식이 훨씬 더 편리하다.

• head ➡️ 가장 앞에 있는 원소의 인덱스
• tail ➡️ 가장 뒤에 있는 원소의 인덱스 +1

 

큐와 다르게 양쪽으로 삭제와 삽입이 모두 가능하기 때문에, 

초기값을 max로 둔다!

 

Deque의 자주 쓰이는 메서드

offerLast(E e)	뒤에 원소 추가	큐 삽입
pollFirst()	앞에서 원소 꺼내고 제거	큐 삭제
peekFirst()	앞 원소 확인 (삭제 X)	큐 조회
offerFirst(E e)	앞에 원소 추가	스택 push
pollFirst()	앞에서 원소 꺼내고 제거	스택 pop
peekFirst()	앞 원소 확인	스택 top

 

 

• add, remove ➡️ 실패시 exception
• offer, poll ➡️ 실패시 false, null
• peek ➡️ 안 꺼내고 원소 확인

 

순환하는 사이클을 가지는 유형의 문제를 풀때 deque를 사용하여 풀이할 수 있다.

 

 

백준 2346번

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

 

package 백준.deque;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;

/*
문제
1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.


 */
public class baekjoon_2346 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] st = br.readLine().split(" ");
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        int count = 1;
        for (String str : st) {
            deque.offer(Integer.parseInt(str));
            map.put(Integer.parseInt(str), count);
            count ++;
        }


        int[] answer = new int[N];
        answer[0] = deque.pollFirst();

        for (int j=0; j<N-1; j++) {
            int peek = answer[j];
            if(peek >= 0) {
                for (int i = 0; i < peek - 1; i++) {
                    deque.offerLast(deque.pollFirst());
                }
                answer[j+1] = deque.pollFirst();
            }
            else {
                peek *= (-1);
                for (int i = 0; i < peek - 1; i++) {
                    deque.offerFirst(deque.pollLast());
                }
                answer[j+1] = deque.pollLast();
            }
        }

        for (int i : answer){
            System.out.print(map.get(i)+" ");
        }
    }
}

 

처음에 hashmap과 deque를 이용해보려고 했는데,

Hashmap의 경우 key값이 중복될 경우 그대로 value 값이 덮어씌워지기 때문에 적절하지 않았다.

출력은 나오지만 매우 이상한 방식이다 (..)

 

String[] st = br.readLine().split(" ");
        ArrayDeque<int[]> deque = new ArrayDeque<>();

        int count = 1;
        for (String str : st){
            int value = Integer.parseInt(str);
            deque.offer(new int[]{count, value});
            count ++;
        }

 

HashMap을 이용하는 대신, ArrayDeque에 int[] 형식을 저장하여 value값과 index 값을 함께 저장하도록 하였다.

 

for (int i=0; i<N; i++) {
            int[] firstBalloon = deque.pollFirst();
            int move = firstBalloon[1];
            int index = firstBalloon[0];
            System.out.print(index + " ");

            if (deque.isEmpty()){break;}

            // [0] 인덱스는 출력, [1]인덱스는 이동할 값으로 사용한다.
            if (move >= 0) {
                for (int j = 0; j < move - 1; j++) {
                    deque.offerLast(deque.pollFirst());
                }
            }
            else {
                move = Math.abs(move);
                for (int j = 0; j < move ; j++) {
                    deque.offerFirst(deque.pollLast());
                }
            }
        }

 

가장 앞쪽에 위치한 풍선정보를 pollFirst()로 꺼내서, firstBalloon[] 배열에 저장한다.

풍선에 적힌 값(value)은 다음에 이동해야할 거리이므로, 이. 값을 move 변수로 저장하였다.

 

 

참고로 음수만큼 이동할 때에는 N-1번이 아니라, N번 이동해야 터뜨릴 풍선이 맨 앞으로 위치한다.