문제

풀면서 어려웠던 점

Greedy 알고리즘을 접할 때마다 느끼지만, '아 이거 너무 막무가내인데..' 라는 생각이 많이 든다. 좀 더 아름답게, 딱딱 떨어지게 풀 수 있을 것 같은데 정말 이게 맞나 싶지만, 그게 답이다.

사실 Greedy문제를 계속 접하는 이유 중에 하나라고 생각한다. 나는 코딩테스트를 보면서 다소 단순무식한 해결방법이 떠올랐을 때, '이건 너무 복잡한데..'라고 지레 짐작해서 그만두는 경우가 많다.
Greedy 알고리즘 문제를 계속 풀면서 입출력 제한, 문제 유형을 눈에 익히고 코딩테스트 때 Greedy 문제가 나오더라도 당당하게 풀이를 밀고 나갈 수 있는 취준생이 되어야 한다.

작성한 코드

package Greedy_Algorithm;

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

public class BOJ_19941_햄버거_분배 {
	
	static int N, K;
	static char[] arr;
	static Queue<Integer> Plist;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		Plist = new LinkedList<Integer>();
		
		arr = new char[N];
		String temp = br.readLine();
		
		for(int i=0; i<N; i++) {
			arr[i] = temp.charAt(i);
			if(arr[i]=='P') {
				Plist.add(i);
			}
		}
		
		int answer=0;
		boolean already=false;
		int size = Plist.size();
		while(!Plist.isEmpty()) {
			int t = Plist.poll();
			for(int i=K; i>0; i--) {
				if(t-i>=0 && arr[t-i]=='H') {
					arr[t-i]='P';
					answer++;
					already=true;
					break;
				}
			}
			for(int i=1; i<=K; i++) {
				if(already) break;
				
				if(t+i<N && arr[t+i]=='H') {
					arr[t+i]='P';
					answer++;
					break;
				}
			}
			already = false;
		}
		System.out.println(answer);
	}

}