[HackerRank] Electronics Shop (Easy) by javascript

▷ 문제 : Electronics Shop (Easy)

Electronics Shop | HackerRank

▷ 해결 날짜 : 2022.04.21
▷ 소요 시간 : 40분
▷ 풀이 과정 :
문제를 보자마자 아 이문제는 이중 반복문이면 바로 해결이 가능하겠구나 싶었으나,

이중 반복문을 사용하게 되면 O(n²)의 시간 복잡도를 가지게 된다.

 

그래서 반복문 한번으로 풀 수 없을까 하다가 while문을 돌리게 됐는데...

다 풀고나니 이게 과연 O(n) 시간 복잡도가 맞는지도 의문이다...

괜히 시간만 오래 썼나 싶기도하고

▷ 구현

function getMoneySpent(keyboards, drives, b) {
    let mostExpensive  = -1;
    let [kIdx, dIdx] = [keyboards.length - 1, drives.length - 1];
    while(kIdx >= 0 && dIdx >= 0){
        const [keyboard, drive] = [keyboards[kIdx], drives[dIdx]];
        const price = keyboard + drive;

        if(price <= b) mostExpensive = Math.max(mostExpensive, price);
        if(kIdx >= 0 && dIdx === 0){
            kIdx--;
            dIdx = drives.length - 1;
        }else dIdx--;
    }
    return mostExpensive;
}

▷ 복기 :
해커랭크에서 시간 복잡도가 안 나오니 이건 또 이거 나름대로 불편하네