[BOJ-11003][슬라이딩 윈도우] 최솟값 찾기 - Java

문제 바로가기

11003번: 최솟값 찾기

시간 제한이 굉장히 빽빽합니다.

슬라이딩 윈도우 개념을 적용하면 풀 수 있는데.. 시간을 줄이기 위한 최대한의 노력을 해야합니다. 

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

public class Main {
	public static void main(String[] args) throws Exception {
		input();
	}

	public static void input() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Deque<Integer> deque = new ArrayDeque<>();		// 인덱스(list[idx] 오름차순)
		
		int N = Integer.parseInt(st.nextToken()); int L = Integer.parseInt(st.nextToken());
		int[] list = new int[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			list[i] = Integer.parseInt(st.nextToken());

			// i-L ~ i 범위 밖에 있는 인덱스 제거
			if(!deque.isEmpty() && deque.getFirst() <= i - L) {
				deque.removeFirst();
			}
			
			// 새로 입력받은 애보다 큰 애들은 deque에서 빼자
			while(!deque.isEmpty() && list[deque.getLast()] > list[i]) {
				deque.removeLast();
			}
			
			deque.offer(i);
			// list[deque.getFirst] 는 i-L ~ i 범위 안에 있고 그 중 가장 작은 수
//			sb.append(list[deque.getFirst()] + " ");	// 시간 초과 ;;
			sb.append(list[deque.getFirst()]).append(" ");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

휴 근데 마지막에 StringBuilder에 추가하는데 

//	sb.append(list[deque.getFirst()] + " ");	// 시간 초과 ;;
	sb.append(list[deque.getFirst()]).append(" ");

왜 이럴까요.. 암튼 이렇게 됩니다... 굉장히 빡빡한가봐요....

 

로직 자체는 어렵지 않습니다... 그 전에 시간초과 뜬 다른 풀이 방법을 간단히 얘기해보자면..

먼저 크기 L인 Deque 을 만들고 stream API 를 써서 최솟값을 구했습니다. 답도 나오고 코드도 단순하지만 아주 무식한 방법이죠. 플레티넘 문제는 호락호락하지 않았슴니다.

 

두 번째로는 우선순위 큐를 썼습니다. 최소 힙을 만든것이죵. 이것도 넣고 빼는데 오버헤드가 컸나..? 쨌든 얄짤없었습니다.

 

 

그래서 여기저기 찾아보고 도움을 받았습니다....

 

통과한 문제의 로직은 이렇습니다. 

Deque에는 인덱스를 넣습니다. 넣을 때는 뒤에서 넣는데, 이때 list[]의 값들을 비교해가면서 새로 들어오는 친구보다 큰 친구들은 Deque에서 빼주는겁니다. 최솟값을 구하는게 문제니깐요. i-L ~ i 범위 사이에 있는지 잘 체크하고, Deque에 들어 있는 인덱스를 갖고 list에 대해 오름차순을 유지해주면 그 범위에 있을 수 있는 수 중에서 가장 작은 수는 항상 list[deque.getFirst()] 가 되는것이죠...

 

 

공부 정말 많이 해야겠습니다... 

감사합니다!!

 

 

 

 

 

Reference

maivve.tistory.com/225