문제이해
이 문제는 사람들과 사람들이 주어지고, 각 사람은 자신의 위치에서 거리가 k이하인 햄버거를 먹을 수 있는데, 만약 누군가가 먹었다면 해당 햄버거는 먹을 수 없습니다.
이 상태에서, 식탁의 길이와 햄버거를 선택할 수 있는 거리가 주어지고, 사람과 햄버거의 위치관계가 주어졌을때 햄버거를 먹을 수 있는 최대 횟수를 구하는 프로그램입니다.
문제접근
이 문제는 그리디 알고리즘을 이용해 해결할 수 있습니다.
그리디 알고리즘이란 매번 현재 상황에서 가장 좋아 보이는 선택을 하면서, 그 선택이 전체 최적의 해를 보장할 수 있을 때 사용하는 알고리즘입니다.
이 문제에서 각 사람은 자신에게 가장 가까운 햄버거를 먹어야, 최대한 많은 사람이 햄버거를 먹을 수 있게 됩니다. 그 이유는, 한 사람이 먼 거리에 있는 햄버거를 선택하면 다른 사람이 가까운 햄버거를 먹을 수 없게 되어 최종적으로 햄버거를 먹을 수 있는 사람의 수가 줄어들 수 있기 때문입니다.
따라서, 가장 가까운 햄버거를 먼저 선택하는 것이 그리디한 선택입니다.
배열의 왼쪽부터 p를 찾고, 해당 p의 왼쪽에 있는 햄버거를 가까운 순서로 선택해야 가장 많은 인원의 사람들이 햄버거를 먹을 수 있게 됩니다.
각 사람의 위치에서 가장 가까운 햄버거를 선택하는 것이 부분 문제가 되고, 이 부분 문제를 전체 사람들에게 적용하면 햄버거를 먹을 수 있는 사람의 최대 명수를 구할 수 있습니다.
햄버거를 가까운 순서대로 선택하면 최적해를 보장할 수 있기 때문에 그리디 알고리즘을 적용할 수 있습니다.
굳이 오른쪽부터 탐색하고싶으면 배열의 오른쪽부터 p를 찾고, 해당 p기준으로 오른쪽에 있는 햄버거를 먼저 선택하는 방식으로 해도 됩니다. 대칭적이니까 !
문제풀이 핵심
이 문제를 풀때 중요한 것은
1. 최적의 해를 위해서는 사람과 가까운 햄버거를 선택해야 하는 것
2. 인덱스를 어떻게 설정할것인지
3. 이미 먹어버린 햄버거를 어떻게 처리할 것인지
위의 세가지가 중요한 것 같습니다.
- 인덱스를 어떻게 설정할것인지
인덱스 설정에서 중요한것은 내가 탐색하려는 햄버거의 범위가 주어진 문자열 범위를 벗어나면 안된다는 점 입니다.
만약, P가 0번 인덱스부터 나왔는데 내가 그 왼쪽에 존재하지도 않는 햄버거를 찾고있음 안되겠쬬 ?
위의 ArrayIndexOutOfBoundsException를 고려하여 인덱스의 범위 최대치와 최소치를 min max를 이용하여 설정하는 것 입니다.
startIdx의 경우에는, max함수를 이용하여 배열이 가질 수 있는 가장 작은 인덱스인 0을 하한으로 삼아 이것보다 큰 범위에 속하는 인덱스만 추출하는 것 입니다.
endIdx의 경우에는, min함수를 이용하여 배열이 가질 수 있는 가장 큰 인덱스인 N-1를 상한으로 삼고, 이보다 더 작은것을 반환하여 내부의 인덱스만 추출해내는 것 입니다.
- 이미 먹어버린 햄버거를 어떻게 처리할 것인지
이미 먹은 햄버거에 대해 탐색하지 않도록 if문 내부에 조건을 걸어주면 됩니다.
code
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main {
static int n;
static int k;
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());
char[] list = new char[n];
boolean[] ate = new boolean[n];
String str = br.readLine();
for(int i=0; i<str.length(); i++){
list[i]=(str.charAt(i));
}
solution(list,ate);
} public static void solution(char[] list, boolean[] ate ){
int answer = 0;
for(int i=0; i<n; i++){
if(list[i]=='P'){
int startIndex = Math.max(i-k,0);
int endIndex = Math.min(i+k, n-1); // 배열을 벗어나지 않도록 인덱스 범위 설정
for(int j = startIndex; j<=endIndex; j++)
{
if(list[j] == 'H' && !ate[j]){
ate[j] = true;
answer ++;
break;
}
}
}
}
System.out.println(answer);
}
}
