백준 1756번 피자 굽기

https://www.acmicpc.net/problem/1756

1756번: 피자 굽기

 

저는 먼저 아래 층에 있는 너비가 위층보다 커도 결국 위층의 너비보다 큰 것이 들어갈 수 없다는 것을 알게되었습니다.

그래서 전처리를 하여 이전 층보다 크거나 같다면 그 너비가 몇개 있는지 확인하고 만약 이전 층보다 작다면 이전 층까지의 개수와 너비를 List에 넣고 다시 너비의 개수를 세어주었습니다.

다음으로는 들어온 너비를 보고 해당 List의 인덱스 역순으로 보면서 해당 너비보다 큰 너비를 찾고 Map을 통해 해당 너비를 몇개 사용했는지를 저장했습니다. 만약 너비가 이 개수보다 크다면 다음 너비를 줄였습니다.

마지막으로 마지막에 넣은 너비의 인덱스까지 너비의 개수를 넣어주고 마지막 인덱스는 너비의 개수 - 사용 개수를 하여 마지막의 피자가 어느 뎁스에 있는지를 확인하였습니다.

 

package BOJ.Simulation;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1756_2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Long> stol = Long::parseLong;

        long n = stol.apply(st.nextToken());
        long m = stol.apply(st.nextToken());

        List<long[]> hole = new ArrayList<>();
        Map<Integer,Integer> usedHole = new HashMap<Integer,Integer>();

        long prev = 1_000_000_000;
        int cnt = 0;
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < n ; i++){
            long num = stol.apply(st.nextToken());
            if(cnt == 0){
                prev = num;
                cnt++;
                continue;
            }
            if(prev <= num){
                cnt++;
            }else{
                hole.add(new long[] {prev,cnt});
                prev = num;
                cnt = 1;
            }
        }
        hole.add(new long[] {prev,cnt});
//        for(long[] now : hole){
//            System.out.println(Arrays.toString(now));
//        }
        st = new StringTokenizer(br.readLine()," ");
        int index = hole.size()-1;
        for(int i = 0 ; i < m ; i++){
            long num = stol.apply(st.nextToken());
            index = downPizza(hole,index,num,usedHole);
            if(index == -1){
                break;
            }
        }
        if(index == -1){
            System.out.println(0);
        }else{
            System.out.println(checkDepth(hole,usedHole,index));
        }
    }

    private static int checkDepth(List<long[]> hole, Map<Integer, Integer> usedHole, int index) {
        int result = 1;
//        System.out.println(index);
        for(int i = 0 ; i < index ; i++){
            result += hole.get(i)[1];
//            System.out.println(result);
        }
        result += (hole.get(index)[1] - usedHole.get(index));
        return result;
    }

    private static int downPizza( List<long[]> hole,int index,long num, Map<Integer,Integer> usedHole) {
        for(int i = index ; i >= 0 ; i--){
            if(hole.get(i)[0] < num){
                continue;
            }else if(hole.get(i)[1] > usedHole.getOrDefault(i,0)){
                usedHole.merge(i,1,(v1,v2) -> v1 + 1);
                return i;
            }
        }
        return -1;
    }
}