[백준 11003] 최솟값 찾기 : Deque

🔎 문제

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

---

🎁 풀이

코테 준비를 위해 Do it! 알고리즘 코딩테스트 책을 보면서 공부하며 만난 문제로, Deque를 활용하여 최솟값을 찾는 문제임을 알 수 있었다. 코테 초보자인 나는 처음 문제를 보고 이중 for문을 사용하여 푸는 방식을 생각했다. 그러나 해당 문제를 이중 For으로 풀 경우 시간 제한에 걸리기 때문에 O(n)의 시간복잡도를 가진 방식을 찾아야했다. 

 

이 문제에서 사용한 자료구조인 Deque란 무엇일까?

Deque(덱)이란, 양 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조로 LinkedList,  ArrayDeque 등으로 구현한다. 

addFirst(), removeFirst() 함수를 통해 맨 앞의 데이터를 삽입, 삭제할 수 있고,

addLast(), removeLast() 함수를 통해 맨 뒤의 데이터를 삽입, 삭제할 수 있다. 

 

해당 문제를 풀 때 아래의 규칙을 이해해야 풀이 방식을 이해할 수 있다. 

1. deque는 최소값 순(작은 숫자 순)으로 정렬된다. 

2. deque의 크기는 윈도우의 크기를 넘어서면 안된다. 

 

이 규칙을 토대로 말로써 문제 풀이 방식을 설명해보면 아래와 같다. 

• Deque에 들어가는 객체(class)의 구조는 index와 value를 포함한다. 
• 기본적으로 Deque.addLast()를 통해 새롭게 들어오는 데이터를 저장한다. 
• 하지만, 마지막 위치에 데이터를 저장할 때 만약 새롭게 들어오는 값보다 기존에 Last에 저장된 값이 더 크다면, 해당 값은 removeLast()를 통해 삭제한다. → 작은 숫자 순으로 정렬
• 그리고, 새롭게 들어온 데이터의 index와 First에 저장된 index의 차이가 윈도우의 크기를 넘어서면 First의 값을 지운다. 
• 위의 규칙이 적용된 deque라면 최소값은 맨 앞(First)에 존재하는 값이므로 getFirst()를 통해 데이터를 조회하여 출력한다. 

 

위에서 풀이한 내용을 java 코드로 작성한 내용이다. 

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

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int countOfNumber = Integer.parseInt(st.nextToken());
        int sizeOfWindow = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        Deque<Node> deque = new LinkedList<>();

        for(int i = 0 ; i < countOfNumber ; i++){
            int now = Integer.parseInt(st.nextToken());

            while(!deque.isEmpty() && deque.getLast().value > now){
                deque.removeLast();
            }
            deque.addLast(new Node(now, i));
            if(i - deque.getFirst().index >= sizeOfWindow){
                deque.removeFirst();
            }
            bw.write(deque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }

    static class Node{
        int value;
        int index;

        Node(int value, int index){
            this.value = value;
            this.index = index;
        }
    }
}

 

코드와 풀이한 내용을 비교하며 설명하자면,

- Deque에 들어가는 객체(class)의 구조는 index와 value를 포함한다. 

 Node class를 아래와 같이 정의하고, Deque에서는 작성한 Node 클래스를 사용하여 저장한다. 

    static class Node{
        int value;
        int index;

        Node(int value, int index){
            this.value = value;
            this.index = index;
        }
    }

 

- 기본적으로 Deque.addLast()를 통해 새롭게 들어오는 데이터를 저장한다. 

- 하지만, 마지막 위치에 데이터를 저장할 때 만약 새롭게 들어오는 값보다 기존에 Last에 저장된 값이 더 크다면, 해당 값은 removeLast()를 통해 삭제한다. → 작은 숫자 순으로 정렬

- 그리고, 새롭게 들어온 데이터의 index와 First에 저장된 index의 차이가 윈도우의 크기를 넘어서면 First의 값을 지운다. 

- 위의 규칙이 적용된 deque라면 최소값은 맨 앞(First)에 존재하는 값이므로 getFirst()를 통해 데이터를 조회하여 출력한다. 

for(int i = 0 ; i < countOfNumber ; i++){
    int now = Integer.parseInt(st.nextToken());

    while(!deque.isEmpty() && deque.getLast().value > now){
        deque.removeLast();
    }
    deque.addLast(new Node(now, i));
    if(i - deque.getFirst().index >= sizeOfWindow){
        deque.removeFirst();
    }
    bw.write(deque.getFirst().value + " ");
}

---

Deque라는 자료구조 활용에 대해 몰랐을 땐 무척 어렵게 느껴진 문제였지만, 어떻게 풀어야 할 지 알고나지 풀이 자체는 어렵지 않았다. 이번 기회를 통해 잘 정리해서 유사한 문제를 풀이 없이 풀 수 있도록 연습해야겠다.