[JAVA] BOJ 백준 11003번 - 최솟값 찾기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

11003번: 최솟값 찾기

---

2. 내가 푼 방법

모든 A (i-L+1) ~ A (i) 인 배열에서 매번 정렬(= 최솟값 찾기)을 하게 된다면 시간초과가 발생할 것이다.

하지만 만약 A (i-L+1) ~ A (i) 배열이 항상 오름차순으로 정렬된다면 바로 맨 앞 값만 가져오면 되는 문제이다.

 

포인트만 잡고 나면 코드 작성은 쉬워졌다. 앞쪽, 뒤쪽 양방향에서 값이 제거되는 상황이 필요할 것 같아서  LinkedList를 사용해야겠다고 생각했고, D (i)를 차례로 구하기 전에 A (i-L+1) ~ A (i) 배열을 조정하는 아래와 같은 작업이 필요했다.

1) 맨 앞 값에 대한 범위 확인

2) 새로 들어온 값에 대한 오름차순

---

3. 자바 코드

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

class B11003 {
    static BufferedWriter bw;
    static int N;
    static int L;
    static int[] arr;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        solution();

        br.close();
        bw.flush();
        bw.close();
    }

    public static void solution () throws IOException {
        LinkedList<Tuple> queue = new LinkedList<>();

        // 초기값 설정
        queue.add(new Tuple(0, arr[0]));
        int count = 1;
        bw.write(arr[0]+" ");

        while (count != N) {
            // 배열 조정 - 1) 맨 앞 값에 대한 범위 확인
            if (queue.getFirst().idx < count + 1 - L) queue.removeFirst();

            // 배열 조정 - 2) 새로 들어온 값에 대한 오름차순
            while (!queue.isEmpty() && queue.getLast().num > arr[count]) {
                queue.removeLast();
            }
            queue.add(new Tuple(count, arr[count]));
            count++;

            bw.write(queue.getFirst().num+" ");
        }
    }

    public static class Tuple {
        int idx;
        int num;

        public Tuple (int idx, int num) {
            this.idx = idx;
            this.num = num;
        }
    }
}

---

4. 결과 및 회고

코드를 작성할 때, 컴파일에러, 런타임에러는 줄이도록 하자.