문제 탐색하기
입력 자료 정리
- N은 이후 입력으로 들어올 문자열의 길이고,
k는 등장하는 모든 사람의 양옆으로 햄버거를 선택할 수 있는 최대 거리다 - 이후 n의 크기만큼 들어오는 문자열은 사람과 햄버거가 섞여있다
해결방법 추론
- 시간제한도 0.5초, n의 크기도 2만으로 완전탐색은 절대 하지 말라는 문제로 보인다
- DP를 써야하나 고민했을 때, 뭔가 누적을 하는 경우를 찾기도 애매하다
- 어떻게 풀어야할지 고민하면서, 이 문제에서 구하고자 하는 목표를 다시 확인했다
- 이 문제의 목표는 햄버거를 최대한 많은 사람이 먹게 하는 것이다.
- 이 목표를 해결하기 위해서는 사람들이 어떤 선택을 해서 햄버거를 집을 수 있을까 고민하였다
- 일단 사람들은 자신의 왼쪽과 오른쪽으로 k범위 이내의 햄버거를 먹을 수 있다
- 그럼 모든 사람이 자신의 왼쪽에서 최대한 k만큼 떨어진 곳에 있는 햄버거를 먹는다면?
그럼 인접한 사람들도 최대한으로 햄버거를 먹을 수 있지 않을까 생각하였다 - 실제 예제입력을 토대로 테스트를 해보았는데,
내가 생각한 방법으로 해야지 인접한 사람들이 햄버거를 먹을 수 있는 경우의 수가 더 늘어났고,
내 생각이 옳았다는 것을 알게 되었다 - 나의 왼쪽에 있는 햄버거 중 최대한 k만큼 떨어진 거리에 있는 햄버거를 먹는 그리디 방법이,
햄버거를 먹을 수 있는 인원을 최대한 구할 수 있는 방법이 된다
시간복잡도 계산
- 그리디 탐색에서 발생할 수 있는 시간복잡도는 얼마나 될까?
- 그리디 탐색을 위해 n만큼 탐색하는 동안 자신의 왼쪽과 오른쪽으로 k만큼 추가로 탐색을 해야한다
- 이때 발생할 수 있는 최대 탐색의 경우는 n x (2 x k)의 경우이다
- n이 모두 사람이고, 내 양옆의 k범위에 햄버거가 없다면 위와 같은 연산이 발생할 것이다
- 따라서 시간복잡도는 O(n x (2 x k))가 발생하며, 40만 정도의 연산이 발생하므로,
0.5초라는 시간제한 안에 해결할 수 있음을 알 수 있다!
코드 설계하기
입력값 상태 관리하기
- 크기와 범위를 나타내는 n과 k는 모두 변수로 관리한다
- 탐색을 편하게 하기 위해 문자열은 char배열로 선언하여, 관리하였다
그리디 탐색 구현하기
- 앞에 있는 사람이 햄버거를 선택한 경우 다시 선택할 수 없으므로,
boolean 타입의 배열을 하나 선언해주었다 - 이때 n만큼 탐색하며, 사람인 경우는 미리 true로 선언하였다
- 정답 출력을 위한 ans를 0으로 초기화하고 그리디 탐색을 시작한다
- n만큼 순회하면서 만약 현재의 문자값이 P(사람)인 경우, 자신의 k만큼의 왼쪽부터 탐색을 시작한다
- 범위를 벗어나지 않도록 탐색하며, 만약 미방문한 햄버거가 있는 경우, 방문 체크를 해주고
이후 오른쪽 범위를 탐색하지 않고 정답값 증가를 위한 isFind 변수도 true 체크해준다 - 오른쪽은 왼쪽에서 발견하지 못했을 때 탐색한다. 왼쪽가 똑같이 진행해준다
- 이후 isFind를 통해 발견여부를 확인하여 발견했으면 ans의 값을 증가시킨다
출력 설계하기
- 완성한 ans를 출력하면 정답이 된다.
정답 코드
(1회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
char[] arr = br.readLine().toCharArray();
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if(arr[i] == 'P'){
visited[i] = true;
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if(arr[i] == 'P'){
boolean isFind = false;
for (int j = i-k; j < i; j++) {
if(j < 0){
continue;
}
if(!visited[j]){
visited[j] = true;
isFind = true;
break;
}
}
if(!isFind){
for (int j = i+1; j < i+k+1; j++) {
if(j >= n){
continue;
}
if(!visited[j]){
visited[j] = true;
isFind = true;
break;
}
}
}
if(isFind){
ans++;
}
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}
문제 링크
Software Developer