[Baekjoon 14465] 소가 길을 건너간 이유 5 - JAVA

[Silver II] 소가 길을 건너간 이유 5 - 14465

문제 링크

성능 요약

메모리: 14960 KB, 시간: 136 ms

분류

누적 합, 슬라이딩 윈도우

문제 설명

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

입력

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

출력

정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다.

문제 풀이

슬라이딩 윈도우(또는 슬라이딩 투 포인터)라는 알고리즘이 등장했다.

연속적인 데이터나 배열에서 고정된 크기의 윈도우(창문)를 이용하여 원하는 연산을 수행하는 알고리즘이다.
주로 배열이나 문자열과 같은 순차적인 데이터에서 부분적인 연산을 효율적으로 수행한다.

아래 예시를 통해 쉽게 이해가 가능하다.

문제: 길이가 N인 배열이 주어지고, 연속된 K개의 원소를 가지는 부분 배열의 합 중 최댓값을 찾아보자!

예시: 배열 [1, 3, -1, -3, 5, 3, 6, 7]와 K=3가 주어진 경우

1. 초기 단계에서는 처음 3개의 원소를 선택하여 부분 배열 [1, 3, -1]을 만든다.
2. 이 부분 배열의 합은 1 + 3 + (-1) = 3 이다.
3. 다음으로 윈도우를 오른쪽으로 한 칸 옮겨서 [3, -1, -3]을 만든다.
4. 이 부분 배열의 합은 3 + (-1) + (-3) = -1 이다.
5. 윈도우를 다시 오른쪽으로 한 칸 옮겨서 [-1, -3, 5]를 만든다.
6. 이 부분 배열의 합은 -1 + (-3) + 5 = 1 이다.

위 과정을 반복하여 계속해서 부분 배열을 만들고 그 합을 구한다.
그리고 각 단계에서 최댓값을 기록하면, 최종적으로는 최댓값을 찾을 수 있다.

슬라이딩 윈도우 알고리즘은 이렇게 윈도우를 이동시키면서 연산을 계속해서 업데이트하며, 전체 데이터를 다시 계산하지 않아도 원하는 결과를 효율적으로 구할 수 있도록 도와주는 알고리즘이다.

슬라이딩 알고리즘을 이해했으면 문제는 쉽게 풀 수 있다.

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

public class Man {
    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 k = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int[] railStatus = new int[100001];

        for (int i = 0; i < b; i++) {
            int blockedIndex = Integer.parseInt(br.readLine());
            railStatus[blockedIndex] = 1;
        }

        int minBlockedCount = Integer.MAX_VALUE;
        int currentWindowBlockedCount = 0;

        for (int i = 1; i <= n; i++) {
            if (i > k) {
                currentWindowBlockedCount -= railStatus[i - k];
            }
            currentWindowBlockedCount += railStatus[i];
            if (i >= k) {
                minBlockedCount = Math.min(currentWindowBlockedCount, minBlockedCount);
            }
        }

        System.out.println(minBlockedCount);
    }
}

코드 풀이

public class Man {
    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 k = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int[] railStatus = new int[100001];

• n, k, b: 철로의 길이, 부분 배열의 길이, 차단된 구간의 수를 입력받는 변수
• railStatus: 배열을 이용해 철로의 각 위치의 차단 여부를 나타내는 배열, 철로의 최대 길이는 10,000으로 지정되어 있음

for (int i = 0; i < b; i++) {
    int blockedIndex = Integer.parseInt(br.readLine());
    railStatus[blockedIndex] = 1;
}

• 차단된 구간의 수 만큼 반복하면서 차단된 위치를 입력받아 railStatus 배열에 1로 표시한다.

int minBlockedCount = Integer.MAX_VALUE;
int currentWindowBlockedCount = 0;

for (int i = 1; i <= n; i++) {
    if (i > k) {
        currentWindowBlockedCount -= railStatus[i - k];
    }
    currentWindowBlockedCount += railStatus[i];
    if (i >= k) {
        minBlockedCount = Math.min(currentWindowBlockedCount, minBlockedCount);
    }
}

• 슬라이딩 윈도우 알고리즘을 활용하여 각 윈도우에서 차단된 구간의 최솟값을 계산한다.
• currentWindowBlockedCount: 현재 윈도우 내의 차단된 구간의 개수를 나타낸다.
• 윈도우가 이동할 때마다 윈도우 내의 차단된 구간 개수를 업데이트하고, 최솟값을 계산한다.

System.out.println(minBlockedCount);

• 모든 윈도우에 대한 계산이 끝난 후, 최소 차단된 구간의 개수를 출력한다.