[프로그래머스] 금과 은 운반하기

https://school.programmers.co.kr/learn/courses/30/lessons/86053

프로그래머스

제한사항

0 ≤ a, b ≤ 10^9
1 ≤ g의 길이 = s의 길이 = w의 길이 = t의 길이 = 도시 개수 ≤ 10^5
0 ≤ g[i], s[i] ≤ 10^9
1 ≤ w[i] ≤ 10^2
1 ≤ t[i] ≤ 10^5
a ≤ g의 모든 수의 합b ≤ s의 모든 수의 합

 

친구와 함께 풀게 되었는데 초기 20분 정도 문제 파악하는데 쓰였음. 제한사항의 범위가 크기 때문에 브루트 포스, dfs, bfs, dp 등은 소거할 수 있었음.

 

친구는 이분 탐색에 대해서 아이디어를 떠올렸고 나는 문제 이해하는데 20분 정도 더 썼음. 결국은 이분 탐색으로 풀이를 선택했지만 제대로 이해하지 못한 상태서 문제를 풀다 보니 구현 중에 많이 막혔음.

• 목표 운반에 걸리는 최적의 시간 범위를 잡고, 이분 탐색으로 해당 시간이 운반량에 적합한지를 비교하여 좌, 우 탐색하도록 함.
• 최악의 경우 10^9 * 10^5 * 2가 예상되며 log2(10^9 * 10^5 * 2) ≈ 47.507회 반복하게 됨.  추가로 각 반복에 도시 길이만 큼 돌아야 하므로 47.507 * 10^5 ≈ 4750699.333회 반복함.

이분 탐색 시 초기 endRange는 해당 문제에서의 최악의 경우 시간이기 때문에 운반량이 1, 시간이 리스트 중에 가장 긴 것을 선택하여 계산함. a, b 총합만큼을 1씩 줄여 반복한다면 최악의 경우라 할 수 있다고 생각함.

• 초기 endRange를 고려할 때 왕복에 대해 고려하지 않아 통과하지 못한 테스트 케이스가 존재함. 따라서 초기 endRange에 2를 곱하여 해결함.

이분 탐색 시 걸린 시간을 기준으로 탐색하고 반복문을 통해 각 도시에서 현재 middle 시간에 대해 금, 은, 광물 운반량을 구하고 총량을 구함. 구한 총량을 통해 필요한 금, 은, 총량을 비교하여 작다면 왼쪽, 크다면 오른쪽을 탐색하도록 구현함.

 

이분 탐색이 익숙지 않아 종료 조건을 구할 때 console.log를 통해 출력해서 middle과 endRange가 같을 때 답을 구하고 반복문을 종료하도록 하였음.

 

총 운반량 계산 시에도 운반 가능한 양과 금, 은 총량에 대해 잘못된 이해로 총량에 더해주는 값을 잘못된 값을 설정. 해당 도시의 운반 가능한 양과 금, 은 총량을 비교하여 처리하도록 수정.

function solution(a, b, g, s, w, t) {
    var answer = -1;
    
    const maxTime = Math.max(...t);
    
    let startRange = 1;
    let endRange = (a + b) * maxTime * 2;
    
    while(1){
        const middle = Math.floor((startRange + endRange) / 2);
        
        if(middle == endRange){
            answer = middle;
            break;
        }
        
        let totalGold = 0;
        let totalSilver = 0;
        let sum = 0;
        for(let i = 0; i < w.length; i++){
            const iter = Math.floor(middle / t[i]);
            const diliver = Math.ceil(iter / 2);
            
            const availableWeight = w[i] * diliver;
            sum += availableWeight >= s[i] + g[i] ? s[i] + g[i] : availableWeight;
            totalGold += availableWeight >= g[i] ? g[i] : availableWeight;
            totalSilver += availableWeight >= s[i] ? s[i] : availableWeight;
        }
        
        if(totalGold < a || totalSilver < b || sum < (a + b)){
            startRange = middle + 1;    
        } else{
            endRange = middle;
        }        
    }
    
    return answer;
}