[자바] 백준 11003 - 최솟값 찾기 (java)

목차

문제 : boj11003

 

 

필요 알고리즘

• 그리디 
  
  • 그리디 개념으로 풀 수 있는 문제이다.
• 덱, 우선순위 큐
  • 생각한 그리디 로직을 구현하기 위해 필요하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 우선순위 큐를 사용한 풀이부터 얘기해보자 (코드2)

코드만 봐도 어떤 느낌인지 알 것 같다. 순서대로 입력값을 넣을 때, 입력값과 위치도 같이 넣는다. 그리고 우선순위 큐에서 최솟값을 꺼낼껀데, 이게 위치가 현재 보고 있는 위치 - L 보다 작으면 버려버리면 된다. 그럼 항상 문제에서 제시된 일정 범위 내의 최솟값이 출력됨이 보장된다.

for (int i = 0; i < n; i++) {
    pq.add(new Num(Integer.parseInt(st.nextToken()), i));	// 입력값을 위치(i)와 함께 저장
    while (pq.peek().idx <= i-l)   pq.poll();	// 최소값을 꺼내는데, 위치가 문제에서 제시된 범위를 벗어난건 버린다.
    sb.append(pq.peek().n).append(' ');	// 위치가 맞는 값 중 최소값이 출력됨이 보장된다.
}

 

  문제는 자바의 경우 자바8과 자바11에 2.6초로 시간 제한이 걸려있다는 것이다. 그래서 위 로직으로는 자바 15 이상으로 제출하면 통과되긴하는데, 자바 15이상이 나중에 백준에 추가되서 제한이 안걸려있던 것이고 의도한바는 2.6초 이내에 되야할 것 같다. 그래서 추가로 짠 코드가 코드1 이다.

 

  pq대신 리스트에 값을 넣는데, 이 리스트는 항상 최선의 상태를 유지하도록 한다. 내 경우 구현을 리스트로 했는데, 덱으로 해도 동일하다. 리스트의 앞쪽에서는 위치 범위가 지난걸 빼고, 뒤쪽으로는 입력받은걸 넣는다. 다만 이 때 리스트에 있는 값 중 가장 마지막값보다 작거나 같은 값일 경우, 어차피 위치 및 값 모두 새로 넣는게 무조건 이득이므로 마지막 값을 빼고 새로운 값을 넣는식이다. 그렇다면 언제나 리스트의 맨 앞은 이 문제에서 요구하는 최솟값임이 보장된다. 그리고 이렇게 풀면 자바 8과 자바 11로도 통과 가능하다. 차이점은 pq는 delete 연산도 O(logN)이 필요하지만 얘는 당연히 O(1)로 가능하기 때문이다.

for (int i = 0; i < n; i++) {
    Num cur = new Num(Integer.parseInt(st.nextToken()), i);
    while (!ll.isEmpty() && ll.getLast().n >= cur.n) ll.removeLast();	// 리스트의 마지막값이 현재값보다 크거나 같은 동안 빼버린다.
    ll.addLast(cur);	// 새로운값을 넣는다.
    while (!ll.isEmpty() && ll.getFirst().idx <= i-l)   ll.removeFirst();	// 위치 범위 지나간건 버린다.
    sb.append(ll.getFirst().n).append(' ');	// 항상 리스트의 가장 앞쪽값이 문제에서 요구하는 최솟값이다.
}

 

 

코드1 (pq 아닌 버전) : github

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
        LinkedList<Num> ll = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            Num cur = new Num(Integer.parseInt(st.nextToken()), i);
            while (!ll.isEmpty() && ll.getLast().n >= cur.n) ll.removeLast();
            ll.addLast(cur);
            while (!ll.isEmpty() && ll.getFirst().idx <= i-l)   ll.removeFirst();
            sb.append(ll.getFirst().n).append(' ');
        }
        System.out.println(sb);
    }
}
class Num implements Comparable<Num> {
    int n, idx;
    public Num(int n, int idx) {this.n=n; this.idx=idx;}

    @Override
    public int compareTo(Num ano) {
        return this.n - ano.n;
    }
}

 

 

코드2 (pq 버전) : github

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
        PriorityQueue<Num> pq = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            pq.add(new Num(Integer.parseInt(st.nextToken()), i));
            while (pq.peek().idx <= i-l)   pq.poll();
            sb.append(pq.peek().n).append(' ');
        }
        System.out.println(sb);
    }
}
class Num implements Comparable<Num> {
    int n, idx;
    public Num(int n, int idx) {this.n=n; this.idx=idx;}

    @Override
    public int compareTo(Num ano) {
        return this.n - ano.n;
    }
}