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

🌵 문제 분석

식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K

사람(P)과 햄버거(H)의 위치가 주어진다.

20 1
HHPHPPHHPPHPPPHPHPHP

 

사람은 자신의 위치로부터 거리가 K 이하인 햄버거만 먹을 수 있다.

예를 들어 K=1이면 사람은 자신과 인접한 햄버거만 먹을 수 있다.

햄버거를 먹을 수 있는 사람의 최대 수를 구하라.

🌵 구현 아이디어

💡 그리디 알고리즘

1. 최대한 멀리 있는 햄버거 고르기

햄버거를 최대한 많은 사람이 먹으려면 한 사람이 햄버거를 고를 때 본인이 닿을 수 있는 거리 중 최대한 멀리 있는 햄버거를 골라야 한다는 아이디어를 떠올렸다.

 

2. 왼쪽에 있는 햄버거부터 고르기

왼쪽 맨 앞에 있는 햄버거부터 차례로 선택해야 뒤에 있는 사람이 햄버거를 먹을 수 있는 기회가 늘어난다.

 

예제 입력 2의 경우 

20 2
HHHHHPPPPPHPHPHPHHHP

1️⃣ 탐색 중 P를 만날 때마다 범위 P-K ~ P+K를 탐색한다.

-> 6번째 위치에서 P를 발견했으니 6-2 ~ 6+2를 탐색한다.

 

2️⃣ 가장 빨리 찾은 H를 먹는다. (이 때 이미 누군가에게 선택된 H는 제외함)

-> 4번째 위치에 H가 있으므로 이 햄버거를 먹는다.

 

이 과정을 모든 P에 대해 수행하면 된다.

🌵 시간 복잡도

모든 P를 탐색 : 식탁의 길이가 N일 때 O(N) -> N은 최대 20,000

P마다 길이 2K의 범위를 탐색 : O(K) -> K는 최대 10

H를 찾은 후 방문 체크 : O(1)

 

따라서 전체 시간 복잡도는 O(N)*O(K)*O(1) = 20,000*10*1 = 200,000

-> 제한 시간(0.5초) 안에 연산 가능하다.

 

🌵 알고리즘

그리디 알고리즘

🌵 코드 설계

1. 입력받기
   1. int 변수에 N, K 입력받기
   2. char[N]에 P, H 입력 받기
   3. boolean[N]으로 이미 먹은 햄버거인지 아닌지 체크하는 배열 생성
2. 그리디 탐색
   1. 배열의 처음부터 탐색
   2. P를 찾으면 P-K ~ P+K를 탐색
   3. H를 찾으면 이미 먹은 햄버거인지 확인
   4. 안 먹은 햄버거이면 먹었다고 방문 체크
   5. 위 과정을 모든 P에 대해 반복
3. 방문 체크된 햄버거의 개수를 출력

🌵 오답 노트

범위를 P-K ~ P+K로 정의한 후 햄버거를 찾을 때

탐색 범위가 0~N을 벗어나는지 확인하지 않아서 오답처리가 되어서 그 부분을 추가해주었다.

//탐색 범위가 table을 벗어나면 다음 인덱스 탐색 시도
    if(j<0 || j>=N) continue;

🌵 정답 코드

import java.io.*;
import java.util.*;

public class Main{
    static int N, K;
    static char[] table;
    static boolean[] check;

    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());

        table = new char[N];
        String str = br.readLine();
        for(int i=0; i<N; i++){
            table[i] = str.charAt(i);
        }

        check = new boolean[N];

        for(int i=0; i<N; i++){
            //사람을 찾음
            if(table[i]=='P'){
                //P-K ~ P+K 범위에서 햄버거 찾기
                for(int j=i-K; j<=i+K; j++){
                    //탐색 범위가 table을 벗어나면 다음 인덱스 탐색 시도
                    if(j<0 || j>=N) continue;
                    //햄버거 찾기
                    if(table[j]=='H'){
                        if(check[j]) continue;
                        check[j] = true;
                        //햄버거를 찾았다면 탐색 중지
                        break;
                    }
                }
            }
        }

        int cnt = 0;

        for(boolean tmp: check){
            if(tmp) cnt++;
        }
        System.out.println(cnt);
    }
}