[JAVA] 백준 19941_햄버거 분배

[문제링크]

https://www.acmicpc.net/problem/19941

 

📌 문제 탐색하기

우선 1-N까지의 위치 중에서 i번째 위치하는 사람은 (N-K) 부터 (N+K)까지 위치로 이동이 가능하고 이 거리안에 있는 H를 먹을 수 있음. 주어진 배열에서 햄버거를 먹을 수 있는 사람의 최대 수를 출력하기 위해서는 2가지 조건을 만족해야함. 조건1. K거리 안에서 H가 이예 존재하지 않는 경우의 수를 사람의 수 ( = 입력받은 P의 개수 )에서 제거한다. 조건2. 조건1 이외에도 이미 주변에 다른 P가 H를 먹어버리는 중복되는 경우가 발생하므로 중복되는 경우들 COUNT해서 제거한다. 조건1과 조건2를 모두 만족하는 경우를 출력하면 정답이라고 생각함.

📌 코드 설계하기

1. 문자열을 배열으로 변환해서 저장하고 
2. 이동이 가능한 거리안에 있는 햄버거가 이미 먹은 햄버거인지 아닌지 여부를 저장하는 배열을 하나 만들어준다.
3. 반복문을 활용해서 우선 체크해야하는 사람 P를 찾고,  해당 사람이 K거리 내에서 먹을 수 있는 햄버거를 찾는다. 이때 햄버거를 먹으면 break; 으로 다음 사람P 체크하는 방식으로 
4. 결과적인 최대 사람 수 출력한다. 

=> 몇일동안 완전탐색으로 문제를 풀었더니 이 문제도 완전 탐색으로 생각하게 됨. 채점 결과 정답이기는 하지만 채점속도가 매우 느림..오래걸림.. 다른 방법도 찾아보기로함. 

📌 가능한 시간복잡도 

각 사람이 K거리 내에서 먹을 수 있는 햄버거를 찾아야하는 문제이니까 가능한 시간복잡도는 O(N * K)이라고 생각합니다. 
( 이때 단점은 이동 가능한 거리는 K의 값에 따라서 커질 수 있는데 이때 속도가 느려지는거 같음 ) 

→ 보안 )  투 포인터 사용

 

📌 정답 코드

import java.util.*;

public class HamburgerEating {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); 
        int K = sc.nextInt();  
        sc.nextLine(); 
        String table = sc.nextLine(); 
        
        char[] arr = table.toCharArray();
        boolean[] eaten = new boolean[N];
        int count = 0;  

        // 모든 위치 탐색 (사람 P 찾기)
        for (int i = 0; i < N; i++) {
            if (arr[i] == 'P') {  
                for (int j = Math.max(0, i - K); j <= Math.min(N - 1, i + K); j++) {
                    if (arr[j] == 'H' && !eaten[j]) {  
                        eaten[j] = true; 
                        count++;  
                        break;  // 가장 가까운 햄버거를 먹었으므로 다음 사람으로 이동
                    }
                }
            }
        }
        System.out.println(count);
    }
}