[BOJ] 11003 - 최솟값 찾기(JAVA)

그냥 이 문제는 자바로 풀지 마세요.

문제

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

11003번: 최솟값 찾기

풀이

기본적으로 일정 구간 안에서 1번의 스캔으로 최소/최대 값을 찾는 문제이다.

단 한번의 스캔으로 O(n) 시간에 풀기 위해서는 deque 자료구조의 삽입/연산을 활용한다.

 

가장 먼저, 전체 구간에서 최솟값을 구하는 방법이다.

배열의 앞에서부터 스캔을 해가면서, 스택에 최솟값을 가진 변수를 계속 넣어주면 된다. 만약, 배열에서 발견한 값이 저장했던 최솟값보다 작을 경우 해당 변수를 배열의 값을 바꿔주고 스택에 넣는 방식이다.

 

그리고, 일정 구간에서 최솟값을 찾기 위해서는 슬라이딩 윈도우 방법과 스택을 활용한다.

가장 먼저, L크기의 deque나 연결리스트를 만들고, 배열의 초기값으로 채워준다.

이후, 새로운 값이 들어올 때 현재 스택의 끝 값보다 작다면 해당 값들을 배열의 값으로 바꿔준다.

 

다만, 이 문제는 자바에 대한 시간을 잘못 줘서 거의 무조건 시간초과가 난다.

이를 해결하기 위해서는 기존에 L 크기의 배열로 채워주지 않고, index를 저장했다가 단 한번만 배열을 넣어주는 것이 필요하다.

 

문제를 풀고 나서 연결리스트의 포인터 연산까지 줄이기 위해 고정된 L+1크기의 배열을 사용해서 구현해봤으나, 최솟값을 갱신해주는 것을 O(L)에서 O(1)로 줄이지 않으면 약 90%에서 시간초과가 났다. 

 

이 문제는 최적화를 극한으로 해야 겨우 풀리는 문제니까 안 푸는 것을 추천한다.

코드

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
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 tk = new StringTokenizer(br.readLine());
        // StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(tk.nextToken());
        int l = Integer.parseInt(tk.nextToken());
        Deque<int[]> linkedList = new LinkedList<>();
        tk = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            int nextInt = Integer.parseInt(tk.nextToken());
            while((!linkedList.isEmpty()) && linkedList.peekLast()[0]>nextInt){
                linkedList.pollLast();
            }
            linkedList.offer(new int[]{nextInt,i});
            if(linkedList.peek()[1]<i-l+1) linkedList.poll();
            bw.write(Integer.toString(linkedList.peek()[0]));
            bw.write(' ');   
        }
        bw.flush();
    }
    
    
}

 

고정 길이 배열을 통해 해결 시도

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
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 tk = new StringTokenizer(br.readLine());
        // StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(tk.nextToken());
        int l = Integer.parseInt(tk.nextToken());
        l++;
        int[] dq = new int[l];
        int end = (n)%l;
        tk = new StringTokenizer(br.readLine());
        int nextInt = Integer.parseInt(tk.nextToken());
        Arrays.fill(dq,nextInt);

        bw.write(Integer.toString(dq[0]));
        for(int i=n-2; i>=0; i--){
            nextInt = Integer.parseInt(tk.nextToken());
            dq[end] = nextInt;
            for(int cnt=0; cnt<l-1; cnt++) {
            	end = (end+1)%l;
            	if(dq[end]>nextInt) {
            		dq[end] = nextInt;
            	}
            	else
            		break;
            }
            end =(i+1)%l;
            bw.write(' ');   
            bw.write(Integer.toString(dq[i%l]));
        }
        bw.flush();
    }
    
    
}