백준 19941번 문제 바로가기

문제에 대한 첫인상

처음에는 deque을 이용해서 풀어보려고 했다. H의 인덱스를 모아놓고 P를 기준으로 K범위에 H 인덱스가 포함되어있으면 pop하고 count을 1 늘리는 방식으로 구현했다. 하지만 사람보다 뒤에 있는 햄버거를 먹지 못하는(?) 알 수 없는 버그가 생겨서 갈아엎고 처음부터 다시 코드를 작성했다.

그냥 greedy하게 이중 for문을 돌려가며 만족하는 (H,P) 쌍이 있을 경우 H을 다른 문자(e.g ‘Y’)로 바꾸고 count을 1 늘리는 방식을 택했다.

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int N, K, count=0;
    string hp;
    
    cin >> N >> K;
    cin >> hp;
    
    for (int i=0; i<N; i++){
        if (hp[i] == 'P'){
            for (int j=i-K; j<i+K+1; j++){
                if (hp[j] == 'H'){
                    hp[j] = 'Y';
                    count += 1;
                    break;
                }
            }
        }
    }

    cout << count;
    return 0;
}