Portfolio

문제

풀이

재영

이분탐색(정확도 100%, 효율성 4,5번 시간초과…)


const solution = (land, P, Q) => {
  let result;

  const flattedLand = land.flat();
  const floorSet = [...new Set(flattedLand)].sort((a, b) => a - b);

  let start = 0;
  let end = floorSet.length - 1;

  let mid = Math.floor((start + end) / 2);

  const getCost = (mid) => {
    if (mid === undefined || mid < 0 || mid > 1000000000) return Infinity;

    return flattedLand.reduce(
      (acc, cur) => (cur < mid ? acc + (mid - cur) * P : acc + (cur - mid) * Q),
      0
    );
  };

  while (start <= end) {
    const midCost = getCost(floorSet[mid]);
    const upperFloorCost = getCost(floorSet[mid + 1]);

    if (midCost < upperFloorCost) {
      if (midCost >= result) {
        break;
      }

      result = midCost;
      end = mid - 1;
    } else {
      start = mid + 1;
    }

    mid = Math.floor((start + end) / 2);
  }

  return result;
};

`for`문으로 리팩토링 + 계산식 최적화하여 해결


const solution = (land, P, Q) => {
  let result;

  const flattedLand = land.flat(); // [여러층값]
  const floorSet = [...new Set(flattedLand)].sort((a, b) => a - b); // [유니크한 값]

// 유니크한 값 모아놓은 이유 - 최적화, 이 유니크한 값에서 그리디적으로 생각하면 최적의 해가 나올 수밖에 없음
// 이유는 +1 -> 무조건 추가비용이 더 들수 밖에 없음 - 1 -> 무조건 제거비용이 들수밖에 없음.

  let start = 0;
  let end = floorSet.length;

  let mid = Math.floor((start + end) / 2); // floorSet에서의 탐색해야 할 범위의 중간

  const getCost = (mid) => {
    if (mid === undefined) return Infinity;
      
    let addBlockCnt = 0; 
    let removeBlockCnt = 0;
    
    for (let i = 0; i < flattedLand.length; i += 1) {
        const diff = mid - flattedLand[i];

        if (diff > 0) {
            addBlockCnt += diff;
        } else {
            removeBlockCnt += diff * -1;
        }
    }

    return addBlockCnt * P + removeBlockCnt * Q
  };

  while (start <= end) {
    const midCost = getCost(floorSet[mid]);
    const upperFloorCost = getCost(floorSet[mid + 1]); // 결정을 무엇으로 할것이냐 - 위층을 비교했을 때 최적화가 가능한지

    if (midCost < upperFloorCost) {
      result = midCost; // 기존의 result 자체를 바꾸는 것 - 이전의 result가 최적의 해가 될 수 있지 않나?
      end = mid - 1;
    } else {
      start = mid + 1;
    }

    mid = Math.floor((start + end) / 2);
  }

  return result;
};

은찬


// 효율성 실패
function solution(land, P, Q) {
    const N = land.length;
    const arr = [];
    let answer = Infinity;
    
    const getAnswer = (arr) => {
        const height = [...new Set(arr)];
        
        for(let i = 0; i < height.length; i++){
            const current = height[i];
            let cost = 0;
            
            for(let j = 0; j < arr.length; j++){
                if(current < arr[j]){
                    cost += (arr[j] - current) * Q;
                } else if(current > arr[j]){
                    cost += (current - arr[j]) * P;
                }
            }
            
            answer = Math.min(answer, cost);
        }
        
    }
    
    for(let i = 0; i < N; i++){
        arr.push(...land[i]);
    }
    
    arr.sort((a, b) => a - b);
    
    getAnswer(arr);
    
    return answer;
}


// 효율성 통과, 정확성 실패
function solution(land, P, Q) {
    // variables and functions
    const N = land.length;
    const arr = [];
    const map = new Map();
    let answer = Infinity;
    
    const getCost = (height, arr) => {
        let cost = 0;
        
        for(let i = 0; i < arr.length; i++){
            if(height < arr[i]){
                cost += (arr[i] - height) * Q;
            } else if(height > arr[i]){
                cost += (height - arr[i]) * P;
            }
        }
        
        return cost;
    }
    
    const binarySearch = (arr) => {
        const height = [...new Set(arr)];
        let front = 0;
        let back = height.length - 1;
        
        while(front < back){
            const mid = Math.floor((front + back) / 2);
            const cost1 = getCost(height[mid], arr);
            const cost2 = getCost(height[mid + 1], arr);
            
            if(cost1 < cost2){
                back = mid;
            } else if(cost1 > cost2){
                front = mid + 1;
            } else{
                break;
            }
            
            answer = Math.min(answer, cost1, cost2);
        }
    }
    
    // start
    for(let i = 0; i < N; i++){
        arr.push(...land[i]);
    }
    
    arr.sort((a, b) => a - b);
    
    binarySearch(arr);
    
    return answer;
}

// 성공
function solution(land, P, Q) {
    // variables and functions
    const N = land.length;
    const arr = [];
    let answer = Infinity;
    
    const getCost = (height, arr) => {
        let cost = 0;
        
        for(let i = 0; i < arr.length; i++){
            if(height < arr[i]){
                cost += (arr[i] - height) * Q;
            } else if(height > arr[i]){
                cost += (height - arr[i]) * P;
            }
        }
        
        return cost;
    }
    
    const binarySearch = (arr) => {
        const height = [...new Set(arr)];
        let front = 0;
        let back = height[height.length - 1];
        
        while(front <= back){
            const mid = Math.floor((front + back) / 2);
            const cost1 = getCost(mid, arr);
            const cost2 = getCost(mid + 1, arr);
            
            if(cost1 < cost2){
                back = mid - 1;
            } else if(cost1 > cost2){
                front = mid + 1;
            } else{
                back = mid - 1;
            }
            
            answer = Math.min(answer, cost1, cost2);
        }
    }
    
    // start
    for(let i = 0; i < N; i++){
        arr.push(...land[i]);
    }
    
    arr.sort((a, b) => a - b);
    
    binarySearch(arr);
    
    return answer;
}

지형 편집

문제

풀이

이분탐색(정확도 100%, 효율성 4,5번 시간초과…)

for문으로 리팩토링 + 계산식 최적화하여 해결

`for`문으로 리팩토링 + 계산식 최적화하여 해결