[Java] 그리디 (햄버거 분배)

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

19941번: 햄버거 분배

 

햄버거 하니까 군 시절에 동기가 행보관님을 햄버거한입으로 저장해 놓은 거 걸려서 엄청 털렸던 기억이 나네요.

 

전형적인 그리디 문제.

가능한 왼쪽부터 먹는 방법으로 O(N*K)로 풀 수 있다.

 

String 배열 array에 입력을 저장하고 반복문을 돌려 해당 위치에 사람이 있다면 그다음 반복문을 실행한다.

 

2차 반복문의 범위는 해당 위치에서 +-K 로 제한. OutOfIndex 오류가 날 수 있기 때문에 조건문을 걸어 방지해 주자.

만약 해당 범위에 햄버거가 있다면 먹었다는 의미로 문자를 E로 교체해 주자.

 

 

 

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int N, K, count=0;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        String[] array = br.readLine().split("");

        for(int i=0; i<N; i++){
            if(array[i].equals("H") || array[i].equals("E")) continue;

            for(int j=(i-K); j<(i+K+1); j++){
                if(j>N-1 || j<0) continue;

                if(array[j].equals("H")){
                    array[j] = "E";
                    count++;
                    break;
                }
            }
        }

        System.out.println(count);
    }
}