[백준(Baekjoon)] 1756. 피자 굽기 (java)

fantastik·2021년 11월 18일
1
post-thumbnail

안녕하세요. 오늘은 백준의 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%까지 채점하다가 틀렸다. 이유를 찾지 못해서 인터넷에서 정답코드를 참고했는데, 확인해보니 이분탐색 구현하는 쪽에서 틀렸다. 문제 풀 때 이분탐색은 많이 접해보지 않아서 자유롭게 구현하는게 어려웠는데, 그래서 틀리지 않았나 싶다. 이분탐색에 대한 확실한 이해가 필요하다고 느꼈다.


[참고한 곳]
https://moons-memo.tistory.com/106

0개의 댓글