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

 

그리디 알고리즘 문제이다.

 

 

 

 

 

 

처음 생각한 접근방식(오답)

 

N이 20000이고, 이러한 크기의 배열을 순회하기 때문에 시간복잡도가 O(N^2) 이상인 알고리즘을 짜면 시간초과가 날 것임이 분명했다.

그래서 그리디 알고리즘을 떠올렸고, 배열을 처음부터 끝까지 한 번만 순회하면서 햄버거를 분배할 수 있는 방법을 찾으려 애썼다. 

사람의 위치를 queue에 넣고 "햄버거"를 기준으로 K만큼 뻗었을 때, 사람의 인덱스보다 크다면 카운트를 증가시키고,

큐에서 팝하는 방식으로 구조를 짰다. 처음에 작성한 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int dict[26];
 
int main(){
 
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N, K;
    cin >> N >> K;
 
    string desk;
    cin >> desk;
 
    queue<int> q;
    for(int i=0; i<N; i++){
        if(desk[i] =='P') q.push(i);
    }
 
    int cnt = 0 ;
    for(int i=0; i<N; i++){
        if(desk[i] =='H' && !q.empty()){
            int next = q.front();
            if(next <= i+K){ //과정 빈약
                cnt++;
                q.pop();
            } 
        }
    }
    cout <<cnt;
    return 0;
}
 
 
 
 

 

물론 이 코드는 당연히 오류가 났고, 그 이유는 예제2의

HHHHHPPPPPHPHPHPHHHP

 

배열에서 연속된 P 다음에 H 인덱스에서는 항상 큐에 있는 사람의 인덱스보다 클 것이기 때문에,

K의 범위를 벗어난 사람까지 햄버거를 먹게 하므로 잘못된 논리이다. 

사실 여기서 막혔던 원인은 "O(N^2)" 시간복잡도를 너무 신경써서 for 구문 두개면 시간 초과가 날 것이라고 생각했던 것이였다.

 

 

합당한 접근방식

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int dict[26];
 
int main(){
 
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N, K;
    cin >> N >> K;
 
    string desk;
    cin >> desk;
 
    int cnt = 0 ;
    for(int i=0; i<N; i++){
        if(desk[i] == 'H'){
            for(int j=max(0, i-K); j<=min(N-1, i+K); j++){
                if(desk[j] == 'P'){
                    cnt++;
                    desk[j] = 'X';
                    break;
                }
            }
        }
    }
    cout <<cnt;
    return 0;
}

 

배열을 앞에서부터 차례로 순회하되, 햄버거를 발견하면, 현재 위치에서 K를 뺀 값(혹은 최소 인덱스 0)부터 현재 위치에서 K를 더한 값(혹은 최대 인덱스 N-1)까지 순회하며 "P"를 찾으면 카운트를 증가시키고 이미 햄버거를 먹였다는 표시를 해준다.

K의 범위는 최대 10으로, 각 H마다 2K번 실행되면 최대 20번이므로 안쪽 for 구문의 수행시간은 O(1)로 봐도 무방하기 때문에 시간초과가 나지 않는다. 이러한 논리를 발견하는 것은 어렵지 않았지만 'K'의 범위를 제대로 인식하지 않아 고정관념에서 벗어나지 못했고, 시간복잡도에 대한 미흡한 공부가 이 문제를 해결하기 어렵게 만들었던 것 같다. 문제의 조건을 잘 확인하고, 시간복잡도에 대한 개념을 확실히 다지자.

 

참고로 "사람"을 기준으로 전개하는 것도 가능하다. 햄버거를 기준으로 사람에게 먹이든, 사람을 기준으로 햄버거를 먹든 논리는 같다.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int dict[26];
 
int main(){
 
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N, K;
    cin >> N >> K;
 
    string desk;
    cin >> desk;
 
    int cnt = 0 ;
    for(int i=0; i<N; i++){
        if(desk[i] == 'P'){ // 'H'가 'P'로 변경
            for(int j=max(0, i-K); j<=min(N-1, i+K); j++){
                if(desk[j] == 'H'){ // 'P'가 'H'로 변경
                    cnt++;
                    desk[j] = 'X';
                    break;
                }
            }
        }
    }
    cout <<cnt;
    return 0;
}
 
 
 

'H'가 'P'로, 'P'가 'H'로 바뀌었을 뿐이다.