[백준]11003 최솟값 찾기 - 자바/Java

11003번: 최솟값 찾기

🌱풀이

💡 시간 초과

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 class Node{
		public int value;
		public int index;
		Node(int value, int index){
			this.value = value;
			this.index = index;
		}
	}
	
	public static void main(String[] args) throws IOException {
		//입력 받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String NL = br.readLine();
		StringTokenizer st = new StringTokenizer(NL);
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		String number = br.readLine();
		st = new StringTokenizer(number);
		
		Deque<Node> mydeque = new LinkedList<>();
		for(int i = 0; i<N; i++) {
			int now = Integer.parseInt(st.nextToken());
			
			//덱에 값이 들어있을 때, 이전 값이 들어올 값보다 크다면 없애야한다.
			while(!mydeque.isEmpty() && mydeque.getLast().value > now) {
				mydeque.removeLast();
			}
			//값 정렬(제거) 후 추가하기
			mydeque.addLast(new Node(now, i));
			
			//범위에서 벗어난 덱 제거
			if(mydeque.getFirst().index <= i-L){
				mydeque.removeFirst();
			}
			bw.write(mydeque.getFirst().value+" ");
		}
		bw.flush();
		bw.close();
	}
}

---

🪴코드 리뷰

• Deque를 사용한 슬라이딩 윈도우라는 측면에서 알고리즘의 로직은 동일하다.
• Deque에 입력하는 자료구조가 다르다. 나는 Node class를 생성하여 저장했고, 아래 풀이자는 Integer형 배열을 입력했다.본인의 풀이가 93%에서 시간초과가 난 걸 보면 미세한 차이로 보인다.
• 노드 클래스를 생성하는게 생각보다 연산 시간을 늘릴 수 있구나.
• 나는 그냥 Deque를 사용했지만, 아래 사용자는 ArrayDequeue를 사용했다.

💡 https://maivve.tistory.com/225

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.valueOf(st.nextToken());
		int l = Integer.valueOf(st.nextToken());
		
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		
		ArrayDeque<Integer> deque = new ArrayDeque<Integer>();	// 배열의 index를 담기 위한 Deque
    // 결과를 배열에 담아도 되고, 바로 StringBuilder에 담아도 된다.
		StringBuilder sb = new StringBuilder();
//		int[] result = new int[n];

		for(int i = 0; i < n; i++) {
			arr[i] = Integer.valueOf(st.nextToken());
			// 범위를 벗어나는 인덱스가 있으면 제거하기(최솟값부터 제거해야 한다. -> 최솟값을 찾고있기 때문에)
//			while(!deque.isEmpty() && deque.peekFirst() <= i - l) {
//				deque.removeFirst();
//			}
			
			if(!deque.isEmpty() && deque.getFirst() <= i - l) {
				deque.removeFirst();
			}
			// 범위 인덱스 내에서 최솟값 인덱스를 넣기 위한 작업.
			// 현재 A[i]보다 큰 것들은 어차피 쓸모없으므로 처분하자.
			while(!deque.isEmpty() && arr[deque.getLast()] > arr[i]) {
				deque.removeLast();
			}
			
			
			deque.offer(i);	// add : 맨앞에서 바깥쪽으로 push. push : 맨 앞에서 안쪽으로 push
			sb.append(arr[deque.getFirst()]).append(" ");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Conclusion

• Dequeue를 이용한 슬라이딩 윈도우 알고리즘을 구현해봤다는데 의의를 뒀다.
• BufferedReader, BufferedWriter를 현업에서도 자주 쓰나..?
• 하긴 메모리나 시간은 아낄수록 좋긴 하겠다.