Javascript(nodejs) 백준 1756 피자 굽기

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

로직

• 구현문제

• 화덕의 깊이, 피자의 크기는 30만

  • 피자가 들어올 때 마다 화덕을 탐색시 최대 30만 * 30만 = 900억번의 연산

• 화덕의 구조가 밑이 아무리 넓어도 위가 좁으면 그 크기를 이용 불가

  • 그렇기에 현재 위치(해당 깊이)에 들어갈 수 있는 크기는 시작부터 현재까지의 최소값

• 한번 위에서 피자를 집어 넣게되면 밑은 사용이 불가능한 구조

• 화덕의 최소값의 변화를 기록하는 Array 생성(변수명 minArray)

• 화덕의 최소값을 몇칸 사용 가능한지 기록(변수명 cnt)

• 피자를 순회 돌며 지름과 minList의 마지막 값과 비교

• 마지막 값보다 피자가 크면 맞는 크기가 나올 떄 까지 minList의 뒷부분 제거

  • 이번 피자를 넣을 수 있는 위치를 깊은곳부터 탐색
  • 이번 피자를 넣게되면 그 보다 깊은 곳은 사용 불가하므로 pop

• 피자를 다 넣을 수 있다면, 현재 남아있는 minList의 값이 몇층있는지 계산

// 함수
function solution(D,N,oven,pizza){
    const [minArray,cnt] = minCheck(oven)
    for (const length of pizza){
        while (minArray.length !== 0){
            if (length > minArray[minArray.length-1]){
                const num = minArray.pop();
                delete cnt[num];
            } else break;
        }
        if (minArray.length !== 0){
            const ovenSize = minArray.at(-1);
            cnt[ovenSize] -= 1
            if (cnt[ovenSize]===0){
                minArray.pop();
                delete cnt[ovenSize];
            }
        } else return 0;
    }
    let answer = 1;
    for (const size of minArray){
        answer += cnt[size];
    }
    return answer;
}
function minCheck(arr){
    const value = new Array();
    const cnt = new Object();
    let minValue = 1000000001
    for (const num of arr){
        if (num < minValue){
            minValue = num
            value.push(minValue)
            cnt[minValue] = 1
        } else cnt[minValue] += 1
    }
    return [value,cnt]
}
// 인풋
const fs = require('fs');
const URI = process.platform === 'linux'? 0:'./1756.txt';
const inputs = fs.readFileSync(URI,'utf-8').toString().trim().split('\n');
const pizza = inputs.pop().split(' ').map(Number);
const oven = inputs.pop().split(' ').map(Number);
const [D,N] = inputs.pop().split(' ').map(Number);
// 실행
const ans = solution(D,N,oven,pizza);
console.log(ans)