https://www.acmicpc.net/problem/19941
백준 실버 3 햄버거 분배 문제를 풀었다.
사실 스터디에서 프로그래머스 문제를 내주시는데 백준 티어 올리고 싶어서 백준을 중심으로 풀고 있다...ㅎ
어쩌다보니 1일 2커밋이 되어가고 있는 ㅎ
위 문제를 보자마자 얼마전 스터디 미들러 문제로 내주신 프로그래머스의 체육복이랑 비슷한 느낌을 받았다.
https://school.programmers.co.kr/learn/courses/30/lessons/42862
그리디 알고리즘을 사용하여 푸는 문제였다.
그리디 알고리즘이 최적해를 찾는 방법인건 아는데 적용하는 방법은 막연했었다.
문제가 단순해서인지 그리디 알고리즘의 특징인지 알고리즘을 몰라도 풀 수 있는 느낌... (그리디 알고리즘 많이 안풀어봄)
그래도 개념이 막연했기 때문에 그리디 알고리즘에 대해 찾아보았다.
https://adjh54.tistory.com/212
그리디 알고리즘
단계마다 최적이라고 생각하는 선택을 하면서 최종적으로 최적의 해를 찾는 과정
그리디 알고리즘 문제의 절차
1. 선택 절차 : 현재 상태에서 최적인 선택하기
2. 적절성 검사 : 선택한 항목이 문제의 조건을 만족시키는지 확인
3. 해답 검사 : 모든 선택이 완료되면 최종 선택이 문제의 조건을 만족시키는지 확인
위 문제를 절차를 생각하며 풀진 않았지만 벨로그를 작성하는 지금 생각해보자면 아래와 같이 되지 않을까 싶다.
선택절차: 범위 내에서 (-k ~ +k) 가장 작은 인덱스에 햄버거가 있는지 확인
적절성 검사: 만약 다른 사람이 먹은건지 확인
해답 검사: 햄버거를 먹은 사람 수를 계산하여 출력
그에 따른 내 코드이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken()); //식탁의 거리
int K = Integer.parseInt(stringTokenizer.nextToken()); //햄버거를 선택할 수 있는 거리
String str = bufferedReader.readLine();
String arr[] = str.split("");
int count = 0;
boolean go;
for (int i = 0; i < N; i++) {
if (arr[i].equals("P")) {
go=true;
for (int j = K; j >= 1; j--) {
if (i - j < 0) {
} else {
if (arr[i - j].equals("H")) {
arr[i - j] = "";
count++;
go = false;
break;
}
}
}
if(go) {
for (int j = 1; j <= K; j++) {
if (i + j >= N) {
break;
} else {
if (arr[i + j].equals("H")) {
arr[i + j] = "";
count++;
break;
}
}
}
}
}
}
System.out.println(count);
}
}문제는 단순했는데 체육복 문제도 그렇고 햄버거 분배도 그렇고 이상하게 테스트 케이스는 정답인데 채점하면 자꾸 틀리다 나와서 고생했다...
질문 게시판 가서 다른 테스트케이스 넣어보니 틀린 부분 알게 됐다.
(저 go 변수 초기화를 이상하게 해서...ㅠ)
(넣어본 테스트 케이스)
8 3
PPHHHHPP
실제 코딩테스트에서는 테스트 케이스가 더 적고 IDE도 못쓴다던데
더 열심히 공부해야겠다 ㅠ_ㅠ
