백준 1654번, 1874번 js 풀이

백준 1654번

1654번: 랜선 자르기

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [K, N] = input.shift().split(' ');
const lines = input.map(Number).sort((a,b) => a-b);

function solution(k, n, nums) {
    let answer = 0;
    let start = 0;
    let end = 10e9; //시작점을 0, 끝 점을 10e9

    function count(mid) {
        let result = 0;
        for (const x of nums) { //x : xcm씩 자른다고 가정했을때 나오는거
            result += Math.floor(x / mid);
        }
        return result;
    }

    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        if (count(mid) < n) {
            end = mid - 1;
        } else {
            answer = mid;
            start = mid + 1;
        }
    }

    return answer;
}

✅솔루션

4,11에 [802,743,457,539]
mid로 나눠진 값으로 (몫)을 더한게 11일경우
11일 경우 중 mid가 제일 큰 경우
-> 그니까 랜선은 xcm 만큼 잘랐을 때 각 랜선에서 얻은 랜선의 개수가 n개보다 많아야 한다.

필요한건 N개인데 n개보다 작다면 너무 길게 자른 것이고 필요한 양만큼 나오지 않기 때문에 길이를 줄여야 한다. 그럼 end = mid - 1; 이렇게 -1을 해줘서 그걸 end로 정하고 다시 돌아가서 더 짧게 자른걸 기준으로 한다는 방식으로 이분 탐색을 하면 되는 것!

n개보다 크거나 같으면 개수는 충분하기 때문에 길이를 더 늘려서 답을 찾을 수 있는지 확인한다. 왜냐하면 최대길이로 최소한으로 만들라했으니!

xcm씩 잘랐을 때 나오는 랜선의 개수를 구하기 위해 각 랜선을 x로 나누었을 때 몫을 취하면 된다.
결국 이분탐색을 사용한다는 것인데 실제 예시를 넣어서 이해하면 쉽다.

---

백준 1874번

1874번: 스택 수열

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = input[0];
var arr = [];
var stack = [];
var answer = '';
for(var i=0; i<cases; i++){
    arr[i] = i+1;
}
for(var j=1; j<=cases; j++){ //4
    var count = 1;
    while(count <= cases && stack[stack.length-1] != input[j]){
        stack.push(arr.shift());
        answer += '+\n';
        count++;
    }
    if(stack[stack.length-1] == input[j]){
        stack.pop();
        answer += '-\n';
    }else{
        answer = 'NO';
        break;
    }
}
console.log(answer);

✅솔루션

입력받는 배열의 길이를 cases로 받아서, 해당 길이만큼 1부터 cases까지의 배열을 arr로 선언해준다
배열의 길이만큼 돌면서 stack의 마지막 값이 input[j]값과 같지않다면 arr에 있는 요소를 계속 stack에 push해준다.

push 할 때에는 +값이 들어가야하므로, answer에 +값을 추가해줌
만약 stack의 마지막 값이 input[j]값과 같아서 while문에서 빠져나오게 된다면,
stack에서 해당 값인 stack의 마지막 값을 pop함수로 꺼내주고, answer에는 -를 추가해주고
하지만, stack의 마지막 값이 input[j]와 같지 않다면, answer에는 NO를 입력해서 반환해줌.