[java] 문제 010 (백준 11003번)

문제

최솟값 찾기

 

교재 풀이

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class P11003_최솟값찾기 {
  public static final Scanner scanner = new Scanner(System.in);

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // 출력을 그때 그때 하는 것보다 버퍼에 넣고 한번에 출력하기 위해 BufferedWriter를 사용
    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());
    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();
  }

  static class Node {
    public int value;
    public int index;

    Node(int value, int index) {
      this.value = value;
      this.index = index;
    }
  }
}

 

설명

이 문제 핵심은 정렬 알고리즘 사용 않고 슬라이딩 윈도우와 덱을 이용해 정렬 효과를 보는 것이다.

 

i-l+1 ~ i 구간은 즉 i-(i-l+1)+1=l이 되네, 즉 구간이 l인 것 중에서 최솟값을 출력해라는 뜻
    왜냐면 예로 1<=x<=5, 즉 1~5인 구간은 총 1,2,3,4,5 길이가 5임. 즉 양쪽 끝값을 전부 포함하면 5-1+1인 셈
    반대로 1<x<=5, 즉 2~5인 구간은 2,3,4,5로 길이가 4임. 즉 부등호 중 하나가 등호가 없으면 5-1만 해주면 됨

 

정렬은 시간 복잡도 문제로 안 됨

=> 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임

 

Deque<자료형> deq=new Linkedlist<>();

=> Deque이란 건 링크드 리스트로 하구나 

 

• Deque에 포함된 함수는 addFirst(), removeFirst(), addLast(), removeLast(), isEmpty(), getFrist(), getLast()가 있다
• Deque<Node>라고 내가 만든 Node를 담은 덱이라면
  • 내가 Node의 속성을 value, index로 해 놓았다면
  • deq.getLast().value 혹은 deq.getFrist().index처럼 덱에 포함된 자료 하나 꺼낸 후 .value, .index처럼 해서 쓸 수 있다

 

24.6.3) 내 풀이 시도만 한...

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

public class Main
{
	public static void main(String[] args) throws IOException{
		N개의 수 A1, A2, ..., AN과 L이 주어진다.
		Di = A(i-L+1) ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.
		    i-l+1 ~ i 구간은 즉 i-(i-l+1)+1=l이 되네, 즉 구간이 l인 것 중에서 최솟값을 출력해라는 뜻
		    왜냐면 예로 1<=x<=5, 즉 1~5인 구간은 총 1,2,3,4,5 길이가 5임. 즉 양쪽 끝값을 전부 포함하면 5-1+1인 셈
		    반대로 1<x<=5, 즉 2~5인 구간은 2,3,4,5로 길이가 4임. 즉 부등호 중 하나가 등호가 없으면 5-1만 해주면 됨
		    이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
	    
	    첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)
	    둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)
	    첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.
	    
	    입력
	        12 3 // 12가 n, 3이 구간 길이인 L 
            1 5 2 3 6 2 3 7 3 5 2 6 // 12개의 수들
        출력 
            1 1 1 2 2 2 2 2 3 3 2 2
                Di = A(i-L+1) ~ Ai 중의 최솟값 -> 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
                a1부터 시작이니, a(1-3+1)~a1의 최솟값이 1 
                a(2-3+1)~a2의 최솟값이 1
                a(3-3+1)~a3의 최솟값이 1 5 2 중 최솟값이니 1이 되고 
                
        
        접근법
            구간 길이 정해졌으니 슬라이딩 윈도우를 활용하면 됨 
            
        슈도 코드
            n, l 입력받고 
            n개의 숫자들을 배열로 받아주고 
                int로 받아도 될 듯, 그리고 크기는 n이든 n+1이든 마음대로 
            
            핵심로직-> 슬라이딩 윈도우 
                투 포인터를 사용해서 구간 정하고 
                각 구간에서 최솟값을 파악하기  -> 탐색 알고리즘은 아님, 시간 초과됨
                    최솟값 탐색은 탐색을 배워야 하지 않나 싶은데 
                    탐색 알고리즘이 n이라면, 포인터가 움직이는 게 n번인데, 
                    만약 l의 길이가 오백만이라면, 포인터로 오백만번 가리키고,
                    또 각 500만 길이의 구간 중 최솟값 찾으려면 
                    n의 제곱이라 10의 12제곱으로 완전 시간 초과임
                내가 한 번 훑었을 때는 새로운 사용자 정의 자료를 만들고 
                    그걸로 뭐 다룬 것 같은데
                    구간 최솟값 구할 때 index, value 두 개를 포함한 data를 만들고
                    정렬을 활용할까? nlogn이라 사용 가능할 듯, 
                        주어진 수들을 담은 배열이 있지
                        그 원래 배열에서 각 원소의 인덱스(배열 몇 번째엿는지)를 파악해서 
                        새 자료형 index와 value 같이 저장하는 거지
                        5의 경우 index는 2, value는 5 이런 식으로
                        
                        그렇게 한 후, 다시 원래 정렬을 오름차순으로 정렬하는거지
                        이 때 정렬할 땐 다시 새로 정의한 자료형인 걸 가지고 배열로 만든 후 
                        ㅡ러면 작은 순대로 1 2 2 2 3 3 3 5 5 6 6 7 뭐 대충 이런식으로 되는데
                        그럼 각 value와 원래 index를 가지고 있고 
                        1 5 
                        
                        
                각 di들을 버퍼라이터에 저장하기 
                
                
            di들을 출력함 
            
	}
}

 

딱히 코드 적은 것 없고

도저히 생각해도 시간 제한 안에 어떻게 접근할 지 감을 못 잡겠어서 다시 교재 봄