백준 11003번: 최솟값 찾기 (JAVA)

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

11003번: 최솟값 찾기

 

 

---

 

 

풀이

풀어내지 못하였다: '회전 초밥'이랑 비슷하다는 느낌이 들어, 안에 들어있는 숫자의 개수를 hash 등에 기록하여 슬라이딩 윈도우를 적용할까 생각해봤는데, 딱봐도 시간초과 각이라서 다른 사람의 풀이를 봤다. 풀고 보니, 회전초밥과의 차이점으로 회전초밥은 현재 슬라이딩 윈도우에서의 종류를 구하기 때문에 중복을 허용하지 않는 HashMap에 기록하면 종류의 개수를 O(1)(=size() 연산)만에 뺄 수 있다는 점이지만, 이 문제는 종류의 개수를 알 필요가 없는 대신 최솟값을 알아야 한다. (적다보니 생각난 풀이인데, TreeMap 쓰면 O(NlogN) 풀이가 가능할 것이다. 그러나, 일단 JAVA에서는 시간초과 뜰 듯.)

풀이: Deque를 활용

기본적인 이해는 https://yabmoons.tistory.com/630에서 했다: 설명이 친절하다.

되게 참신한 문제였다.

0) 일단, Deque deque == (현재/앞으로 최솟값이 될 후보군을 입력 순서대로 보관하는 덱)이다.

1) 슬라이딩 윈도우를 움직이면서,

 1-1) 넣는 원소: deque의 뒤에서부터 비교하면서, 현재 원소보다 크거나 같은 원소를 다 뺀 후(왜냐? index가 현재 넣는 원소보다 작으면서 큰 값은 남은 '수명'동안 현재 넣는 원소보다 크거나 같기 때문에 최솟값이 될 수 없다.) 현재 원소를 넣는다.

 1-2) 빼는 원소: 빼는 원소의 index값과 deque의 맨 앞 원소의 index가 동일하면 해당 원소를 뺀다(만약 빼는 원소의 index값을 가진 원소가 deque에 없다면, 이는 해당 index의 원소는 최솟값의 후보가 아니어서 deque에서 제외된 것이다.).

 1-3) 당연히, deque가 비어있는 경우 넣는 작업만 하면 된다.

2) 설명을 보면 deque 내의 원소는 값과 index가 필요하다: int[]로, {값, index}을 저장하도록 한다.

 

 

 

궁금한 점

1) index 안 기록해줘도 되지 않을까? (코드 2 풀이)

2) 왜 index 기록하는 풀이가 기록 안 하는 풀이보다 속도가 빠를까?

이와 별개로, JAVA로 코드 작성 시 최적화해도 백준 서버 컨디션에 따라 TLE가 뜨기도 한다. 시간 제한이 많이이 빡빡한 문제인 듯하다. 

 

 

코드

풀이 1: 정답(일반적인 풀이(https://loosie.tistory.com/324))

import java.io.*;
import java.util.*;

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 n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());

        Deque<int[]> q = new ArrayDeque<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(st.nextToken());
            while(!q.isEmpty() && q.peekLast()[0] > num) q.pollLast();

            q.offer(new int[] {num,i});
            if(q.peek()[1] < i -(l-1)) {
                q.poll();
            }
            bw.write(q.peek()[0]+" ");
        }
        bw.flush();
        bw.close();
    }
}

 

 

코드 2: 내 풀이(특별히 틀린 점은 없는 듯한데 시간초과가 뜬다)

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

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 N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] nums = new int[N+1];

        ArrayDeque<int[]> deque = new ArrayDeque<>(); // '후보군'을 넣는 deque
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            while (!deque.isEmpty() && deque.peekLast()[0] > nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(new int[] {nums[i], i});
            if (deque.peekFirst()[1] < i-L+1) deque.pollFirst();
            bw.write(deque.peekFirst()[0]+" ");
        }
        bw.flush();
        bw.close();
    }

}