안녕하세요. 오늘은 백준의 1756. 피자 굽기 문제를 풀어보겠습니다.
1) 문제 링크
https://www.acmicpc.net/problem/1756
2) 맞은 코드 문제 풀이
✔ 내림차순으로 input된 오븐을 오름차순으로 저장해줌
오븐 input 값은 예시 테스트 케이스(5 6 4 3 6 2 3)처럼 내림차순으로 입력됩니다. 저는 내림차순이 햇갈려서 input받을 때 오름차순으로 바꿔버렸습니다.
테스트 케이스에서 5 6 4 3 6 2 3 으로 입력받은 값이 oven배열에는 {3, 2, 6, 3, 4, 6, 5} 이렇게 저장되도록 바꿔주었습니다.
✔ 오븐 모양을 맞춰줌
이분탐색이 가능하도록 밑으로 갈수록 좁아지게 오븐의 모양을 맞춰줍니다. 테스트케이스의 경우 3, 2, 6, 3, 4, 6, 5 -> 2 2 3 3 4 5 5로 오븐의 모양이 맞춰집니다.
제가 선언한 오름차순 oven배열에서는 oven[i]가 oven[i+1]보다 작거나 같아야 합니다.
✔ 오븐 이분탐색 실시
마지막줄에 input받은 피자 반죽 값을 이분탐색으로 찾아야 할 pivot으로 두고 oven배열을 탐색합니다.
3) 틀린 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int depth = Integer.parseInt(st.nextToken());
int pizzaNum = Integer.parseInt(st.nextToken());
int answer = 0;
int[] oven = new int[depth];
int[] pizzaSize = new int[pizzaNum];
//오븐모양을 순서를 바꾸며 입력받고, 왼쪽 index에 위치한 오븐크기가 오른쪽 index에 위치한 오븐보다 작도록 맞춰주는 부분
st = new StringTokenizer(br.readLine(), " ");
for (int i = depth - 1; i >= 0; i--) {
oven[i] = Integer.parseInt(st.nextToken());
if (i != depth - 1) {
oven[i] = oven[i] > oven[i + 1] ? oven[i + 1] : oven[i];
}
}
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < pizzaNum; i++) {
pizzaSize[i] = Integer.parseInt(st.nextToken());
}
if (oven[depth - 1] < pizzaSize[pizzaNum - 1]) {
System.out.println(answer);
return;
}
for (int i = 0; i < pizzaSize.length; i++) {
if (answer != Integer.MIN_VALUE) {
answer = binarySearch(oven, pizzaSize[i], answer);
}
if (answer == Integer.MIN_VALUE) {
answer = 0;
System.out.println(answer);
return;
}
}
System.out.println(depth - answer);
}
private static int binarySearch(int[] oven, int pizza, int index) {
int right = oven.length; //최고
int left = index; //최저
while (left <= right) {
int mid = (left + right) / 2;
if (oven[mid] < pizza) {
left = mid + 1;
} else if (oven[mid] == pizza) {
right -= 1;
} else {
right = mid - 1;
}
}
if (left == index) left += 1;
if (left > oven.length - 1) return Integer.MIN_VALUE;
return left;
}
}4) 정답 참고하여 작성한 맞은 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int depth = Integer.parseInt(st.nextToken());
int pizzaNum = Integer.parseInt(st.nextToken());
int answer = 0;
int[] oven = new int[depth];
//오븐모양을 순서를 바꾸며 입력받고, 왼쪽 index에 위치한 오븐크기가 오른쪽 index에 위치한 오븐보다 작도록 맞춰주는 부분
st = new StringTokenizer(br.readLine(), " ");
for (int i = depth - 1; i >= 0; i--) {
oven[i] = Integer.parseInt(st.nextToken());
if (i != depth - 1) {
oven[i] = oven[i] > oven[i + 1] ? oven[i + 1] : oven[i];
}
}
int lowIndex = -1;
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < pizzaNum; i++) {
int pizza = Integer.parseInt(st.nextToken());
lowIndex = binarySearch(oven, pizza, lowIndex);
if (lowIndex == -1) break;
}
if (lowIndex != -1) answer = depth - lowIndex;
System.out.println(answer);
}
private static int binarySearch(int[] oven, int pizza, int index) {
boolean flag = false;
int high = oven.length - 1; //최고
int low = index + 1; //최저
while (low < high) {
int mid = (low + high) / 2;
if (oven[mid] < pizza) {
low = mid + 1;
} else {
high = mid;
flag = true;
}
}
if (flag) return high;
else return -1;
}
}5) 틀린 이유/ 느낀점
✔ 이분탐색 코드 틀림(예제케이스는 찾지 못함)
처음에 틀린 코드로 제출했을 때 75%까지 채점하다가 틀렸다. 이유를 찾지 못해서 인터넷에서 정답코드를 참고했는데, 확인해보니 이분탐색 구현하는 쪽에서 틀렸다. 문제 풀 때 이분탐색은 많이 접해보지 않아서 자유롭게 구현하는게 어려웠는데, 그래서 틀리지 않았나 싶다. 이분탐색에 대한 확실한 이해가 필요하다고 느꼈다.
Backend Developer