BOJ 19941 햄버거 분배(Java)

문제 탐색하기

식탁의 길이와 선택 가능한 거리, 그리고 식탁 위의 사람과 햄버거의 위치가 입력으로 주어진다.

# 예제 입력 1
20 1
HHPHPPHHPPHPPPHPHPHP

# 예제 출력 1
8

# 예제 입력 2
20 2
HHHHHPPPPPHPHPHPHHHP

# 예제 출력 2
7

코드 설계하기

• 사람들은 K 거리 이하에 있는 햄버거를 먹을 수 있다.
  • [-K ~ K ] 범위 내여야 한다.
• 햄버거를 먹을 수 있는 최대 인원을 결과로 출력한다.

시간 복잡도

• 각 사람마다 최대 2K + 1 범위를 탐색한다.
• 시간 복잡도는 정확히는 O(N×(2K+1))이지만, Big-O 표기법에서는 상수를 생략하므로 O(N × K)가 된다.
• 최악의 경우 연산 수는 20,000×(2×10+1)=20,000×21=420,000 이다.

K 값이 크지 않기 때문에, 시간(0.5초) 내에 풀 수 있다.

구현 방법

• 최대 인원이 되려면, 모든 사람들이 먹을 수 있는 햄버거 중 가장 좌측에 위치한 햄버거를 먹어야 다음 사람이 햄버거를 먹을 수 있다. => Greedy Algorithm
  • 예를 들어, 다음과 같은형태 입력에서는 첫번째 사람이 오른쪽 햄버거를 먹으면 두번째 사람은 햄버거를 먹을 수 없다.
  • 첫번째 사람이 좌측 햄버거를 먹으면 두번째 사람도 햄버거를 먹을 수 있다.

4 2
HPHP

1. 입력 정보들을 전역 변수로 선언 후 입력받는다.
2. 햄버거를 먹는 최적의 경우를 탐색하자.
   1. 사람 위치가 아닌 경우 다음 iteration을 수행한다.
   2. 사람 기준으로 가장 좌측부터 가장 우측 K번째 까지 탐색한다.
   3. 먹을 수 있는 조건인 경우, 햄버거를 먹은 상태 배열로 변경하고 먹은 사람 수를 늘린다. 해당 iteration은 종료해야 한다.
3. 결과를 출력한다.

정답 코드 (Java)

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class boj19941 {  
    private static int N, K, cnt;  
    private static char[] arr;  
  
    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());  
  
        // 배열 입력받기  
        arr = br.readLine().toCharArray();  
  
        solve();  
  
        System.out.println(cnt);  
        br.close();
    }  
  
    private static void solve() {  
        for (int i = 0; i < N; i++) {  
            // 사람 위치가 아닌 경우 다음 iteration 수행
            if (arr[i] != 'P') {  
                continue;  
            }  
  
            // 사람 기준으로 제일 왼쪽 K번째 ~ 제일 오른쪽 K번째 (가능한 위치)  
            for (int j = i - K; j <= i + K; j++) {  
                // 현재 위치에서 햄버거를 먹을 수 있는 가장 좌측 위치를 찾고,   
// 먹은 햄버거를 처리한다.  
                if (isEdible(j)){  
                    arr[j] = ' ';  
                    cnt++;  
                    break;  
                }  
            }  
        }  
    }  
  
    private static boolean isEdible(int j) {  
        return j >= 0 && j < N && arr[j] == 'H';  
    }  
}