[JAVA] 백준 q11003 - 최솟값 찾기

11003번: 최솟값 찾기

---

> 의식의 흐름

priority queue와 deque을 같이 쓰면 괜찮지 않을까?라는 생각과 함께 시도했으나 시간 초과,,,

시간복잡도가 괜찮은줄 알았는데 "priority queue의 remove(Object o) 시간복잡도 = O(N)" 이었고 결과적으로 O(N*N)의 시간복잡도를 가지게 되어 시간 초과가 난 것이었다.

어떻게 하면 시간복잡도를 줄일 수 있을까 고민고민했지만 결국 포기하고 풀이를 찾아봤당😅

 

> 풀이

** deque의 삽입, 삭제 연산이 O(1)을 가지는 것을 최대한 활용 **

1. 사용자의 입력값 하나씩 받기

2. 만약 Di = Ai-L+1 ~ Ai에서의 i-L+1 > 1이고 deque의 가장 앞에 있는 Num의 idx가 i-L+1보다 작은 경우.
    오래된 값이므로 제거해야 한다.

• Num 클래스 - idx(사용자의 입력 순번), value(입력값)을 가짐

3. 사용자의 입력값이 deque의 가장 마지막 Num의 value보다 작은 경우,
    deque의 가장 마지막 Num은 이후에도 사용할 일이 없는 값이므로 deque에서 제거

    => 최종적으로 값이 작은 순으로 Num이 저장된다.

4. 사용자의 입력값을 deque에 삽입한다.

5. deque의 가장 앞에 있는 Num의 value가 최소값이므로 해당값을 출력한다.

6. N번 동안 1~6 과정을 반복한다.

 

> 코드

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

public class Main {
    public static int N, L;
    public static Deque<Num> dq = new ArrayDeque<>();

    public static class Num{
        int idx; // 들어온 순서
        int value; // 값

        public Num(int idx, int value){
            this.idx = idx;
            this.value = value;
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++){
            int inputNum = Integer.parseInt(st.nextToken());

            if(i-L>0 && dq.peekFirst().idx<i-L+1){
                // i-L+1>1 => A의 첫범위가 A2~, A3~ ...이고
                // dq의 맨 앞에 있는 Num의 idx가 i-L+1보다 작은 경우
                // 가장 오래된 값 빼기
                dq.pollFirst();
            }

            while(!dq.isEmpty()){ 
                if(dq.peekLast().value>inputNum) // inputNum이 dq의 마지막값보다 작은 경우
                    dq.pollLast(); // dq 마지막값 제거
                else
                    break;
            }

            dq.addLast(new Num(i, inputNum)); // inputNum dq에 삽입
            bw.write(Integer.toString(dq.peekFirst().value)+" ");
        }

        bw.flush();
    }
}