[자바] 백준 14465 - 소가 길을 건너간 이유 5 (java)

 문제 : boj14465

---

 

필요 알고리즘 개념

• 슬라이딩 윈도우, 누적합 알고리즘, 투 포인터 중 하나
  
  • 세가지 방식 모두 구현이 가능하다. 당연히 다른 방법도 있을 수 있다.

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

 

---

 

풀이

  1부터 N까지 나타낼 수 있는 배열을 만들고, 고장난 신호등은 1, 정상인건 0이라고 하자. 이 경우 연속된 모든 K개의 구간의 합이 곧 해당 구간의 고장난 신호등의 갯수 = 수리해야 하는 신호등의 갯수가 된다.

 

  예를들어 예제 입력 1을 생각해보자.

10 6 5
2
10
1
5
9

이걸 위에서 말한대로 배열로 표현해보면 아래와 같다. idx 0번은 사용하지 않는다.

 

  이 때 K가 6이므로, [1, 6], [2,7], ... , [5, 10] 이 모든 연속하는 K개의 구간이 된다. 해당 구간의 배열 합계 중 최소수치를 출력하면 답이 된다. 이하는 예제 입력 1의 모든 경우를 확인한 것으로, [3, 8] 구간의 합이 '1'로 최소이므로 1이 답이 된다.

 

  그럼 이걸 쉽게 구현 가능한 알고리즘이 무엇인지 생각해보면 되는데 누적합 알고리즘, 슬라이딩 윈도우, 투 포인터 알고리즘 정도를 사용해주면 된다. 이 중 누적합 알고리즘은 적어둔 글이 있으므로 잘 모른다면 이 글을 참고해보자.

 

  이하 코드는 누적합과 슬라이딩 윈도우로 구현한 코드이다. 기본형태의 구현이므로 해당 알고리즘만 알고 있다면 구현 자체는 어렵지 않을 것 같다.

 

---

 

코드(누적합) : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int[] arr = new int[n+1];
        while (b-->0) arr[Integer.parseInt(br.readLine())] = 1;
        for (int i = 1; i <= k; i++)
            arr[i] += arr[i-1];

        int min = arr[k];
        for (int i = k+1; i <= n; i++) {
            arr[i] += arr[i-1];
            min = Math.min(min, arr[i]-arr[i-k]);
        }
        System.out.println(min);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

코드(슬라이딩 윈도우) : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int[] arr = new int[n+1];
        while (b-->0) arr[Integer.parseInt(br.readLine())] = 1;
        int sum = 0;
        for (int i = 1; i <= k; i++)
            sum += arr[i];

        int min = sum;
        for (int i = k+1; i <= n; i++) {
            sum += arr[i] - arr[i-k];
            min = Math.min(min, sum);
        }
        System.out.println(min);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}