Minimum Loss

사이트: HackerRank
난이도: 미디움
분류: Search

문제

Lauren은 향후 몇년간의 부동산 가격 예측 차트를 가지고 있다. 그녀는 1년 안에 집을 사고 이후 연도에 팔아서 손실을 최소화 해야 하는데, 이 때 최소 손실액을 반환하라.

1. 나의 풀이

처음 문제를 접했을 때 투 포인터로 작성해야 하나? 라는 생각을 쉽게 떨쳐버릴 수 없었다. 투 포인터 알고리즘을 가지고 계속 조건을 대입해보면서 풀다가 시간이 많이 지체 되었고, 일단은 해결할 수 있는 가장 단순한 수준의 코딩을 작성하게 되었다.
좀 더 머리를 비우고 문제를 바라볼 필요가 있는 듯 하다. 보통 이런 문제들의 풀이는 비슷한 경우가 많기 때문이다.

function minimumLoss(price) {
    // Write your code here
    let min = Infinity;

    for (let i = 0; i < price.length; i++) {
        for (let j = (i + 1); j < price.length; j++) {
            const loss = price[i] - price[j];
            if (loss >= 0) {
                min = Math.min(loss, min);
            }
        }
    }

    return min;
}

2. 다른사람의 풀이

아래와 같이 작성 하면 시간 복잡도 O(n + m) 안에 해결할 수 있다고 한다.
해당 문제와 같이 배열 안의 랜덤한 수의 값 비교 후 가장 작은 차이를 얻는 경우는 정렬을 이용하여 푸는 문제가 많은 것 같다. 이런 점을 잘 기억하고 다음 문제부터는 응용해야 할 것 같다.

function minimumLoss(price) {
  	// 전체 가격별 인덱스를 기록할 변수를 하나 정의한다.
    const indexes = {};
    let minLoss = Infinity;

    for (let i = 0; i < price.length; i++) {
      	// 가격별 인덱스 기록
        indexes[price[i]] = i;
    }
    
  	// 가격을 내림 차순으로 정렬한다.
    price.sort((a,b) => b-a);
  
    for (let i = 1; i < price.length; i++) {
      	// 집을 산 순서보다 이후 인지 확인한다.
        if (indexes[price[i-1]] < indexes[price[i]]) {
          	// 맞을 경우 손실액이 최소인지 비교하고 저장한다.
            minLoss = Math.min(minLoss, price[i-1] - price[i]);
        }
    }
    return minLoss;
}