[백준/Java] 19941 햄버거 분배

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

19941번: 햄버거 분배

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main  {
    static int N;
    static int K;
    static char[] word;
    static int cnt=0;
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb= new StringBuilder();

        st=new StringTokenizer(br.readLine());

        N=Integer.parseInt(st.nextToken());
        K=Integer.parseInt(st.nextToken());

        word = br.readLine().toCharArray();

        for(int i=0;i<N;i++){
            if(word[i]=='P') {
                int index = Math.max(i - K, 0);
                boolean check=false;
                //가장 먼저 발견한 햄버거 탐색
                for(int j=index;j<i;j++)
                {
                    if(bergerCheck(j)){
                        check=true;
                        break;
                    }
                }
                if(!check)
                {
                    index=i+K>=N? N-1: i+K;
                    for(int j=i+1;j<=index;j++){
                        if(bergerCheck(j))
                            break;
                    }
                }
            }
        }
        System.out.println(cnt);

    }
    static boolean bergerCheck(int index){
        if(word[index]=='H'){
            word[index]='X';
            cnt++;
            return true;
        }

            return false;

    }
}
//햄버거와 사람이 주어졌을 때,
//사람의 위치-K~사람의 위치+K까지의 햄버거를 먹을 수 잇는데, 가장 왼쪽에 있는 햄버거를 먹는것이 다음 사람을 위해 좋은 선택이다.

코테 준비가 처음이라 그리디 알고리즘 문제를 많이 접해보지 못했었는데,

이 문제를 풀면서 최선의 수를 선택한다는 것이 어떤 의미인가를 직관적으로 접해볼 수 있어 좋았던 것 같습니다.

다음 사람을 위해(햄버거를 먹을 수 있는 가능성을 높이기 위해) 최대한 왼쪽에 있는 햄버거를 먹도록 차례대로 찾다보니 어렵지 않게 해결 할 수 있었습니다.

코테 스터디 11기의 마지막 포스팅인 것 같은데, 8주간 알고리즘 훈련을 통해 많은 유형과 높은 난이도의 문제를 접하며 벽을 느끼기도 했었습니다.

하지만 방학 전 실5~실4문제도 버거워하던 제가 골드 3~골드2 문제도 때때로 해결하는 수준까지 올라온 것을 보면, 생각을 코드로 옮기는 수준이 한 단계 높아진 것 같아 뿌듯합니다 ㅎㅎ

물론 아직 갈 길이 매우 많이 멀지만, 어떻게 공부를 해나갈지 알게 되었다는 것으로 만족스러운 활동이 되었던 것 같습니다!