[JAVA] 19941번 - 햄버거 분배
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
문제 아이디어)
각 단계에서 가장 좋은 선택을 하는게 결국 문제에서 요구하는 최대한 많은 사람이 햄버거를 먹을 수 있는 것이다.
이 문제에서 가장 좋은 선택: 현재 사람이 자신의 위치에서 먼저 발견된 햄버거를 선택하는것
만약 k가 4라면 최대 4칸떨어진 곳의 햄버거까지 먹을 수 있는데 최대한 먼저 발견된 햄버거를 먹어야 많은 사람들이 햄버거를 먹을 수 있다.
각 단계에서의 선택이 결국 최적의 선택이므로 그리디로 풀 수 있다.
문제 풀기)
char배열에 햄버거와 사람을 입력받는다.
방문 배열을만들어서 방문한 곳은 햄버거를 먹은거니까 다시 탐색하지 않게 해준다.
식탁을 탐색하면서 최대 햄버거를 먹을 수 있는 인원을 찾는다.
시간복잡도
식탁의 길이만큼 반복하면서 탐색범위는 i-k ~ i+k까지 탐색을해야하니까
이중 for문이 필요하다.
식탁의 길이 최대 n * 햄버거 찾는범위 최대 2k+1 이므로
O(n * k) = O(20,000 * 10) = 200,000번의 연산이 필요하고, 0.5초내에 가능하다!
코드 설계하기
위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성
1. 햄버거 먹을 수 있는 최대 사람 수
식탁의 개수만큼 반복문을 돌면서
햄버거를 먹을 수 있는 범위만큼 또 for문으로 탐색을 해준다.
사람의 인덱스를 기준으로 왼쪽으로 최대 i-k만큼 떨어진곳의 햄버거부터
오른쪽으로 최대 i+k만큼 떨어진 곳의 햄버거를 먹을 수 있기 때문에 이렇게 탐색 범위를 지정한다
해당 인덱스가 사람이고 j인덱스가 햄버거이고 방문하지않았다면(그 위치의 햄버거 안먹음)
z카운팅하고 먹었다고 true로 표시한다
for(int i=0; i<n; i++) {
for(int j = Math.max(0, i - k); j <= Math.min(n - 1, i + k); j++) {
if(arr[i]=='P') {
if(arr[j]=='H' && !visited[j]) {
cnt++;
visited[j]=true;
break;
}
}
}
}
시도 회차 수정 사항
- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
1회차 시도
=> 햄버거 탐색 범위를 이렇게 지정해서 틀렸다.
이렇게 범위를 지정하면 배열의 경계를 벗어날 수 있다. i-k이 0보다 작을 경우, i+k이 배열크기 n보다 클 경우
ArrayIndexOutOfBoundsException 에러가 발생할 수 있음
for (int j = i - k; j <= i + k; j++)
정답코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
static int k;
static char[] sign;
static List<String>ans;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
char [] arr = new char[n];
boolean [] visited = new boolean[n];
String input = br.readLine();
for(int i=0; i<n; i++) {
arr[i] = input.charAt(i);
}
int cnt=0;
for(int i=0; i<n; i++) {
for(int j = Math.max(0, i - k); j <= Math.min(n - 1, i + k); j++) {
if(arr[i]=='P') {
if(arr[j]=='H' && !visited[j]) {
cnt++;
visited[j]=true;
break;
}
}
}
}
System.out.println(cnt);
}
}