백준 19941번: 햄버거 분배[JAVA]

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

19941번: 햄버거 분배

 

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        char[] arr = br.readLine().toCharArray();
        int count = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] == 'P') { // 사람일 경우
                int startIndex = Math.max(i - K, 0); // 0보다 작으면 안됨
                int endIndex = Math.min(i + K, N - 1); // 배열의 끝을 넘어가면 안됨
                for (int j = startIndex; j <= endIndex; j++) {
                    if (arr[j] == 'H') {
                        count++;
                        arr[j] = 'X'; // 햄버거가 있다면 햄버거자리를 임의의 문자로 대체
                        break;
                    }
                }
            }

        }
        System.out.println(count);
    }
}

 

[설명]

이 문제는 그리디 알고리즘 문제이다. 슬라이딩 윈도우 처럼 시작인덱스와 끝인덱스를 설정한 후 이동해 나아가면 햄버거를 찾고, 햄버거를 찾았다면 다른 사람이 햄버거를 중복으로 찾는 경우가 발생할 수 있기 때문에 햄버거를 찾았다면 임의의 문자로 대체하고 break로 빠져나온다.