[프로그래머스] 과일장수 (런타임 에러 문제점 찾는 법)

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

 

 

<1번째> 

먼저 score을 sort한뒤 큰 수부터 m개씩 박스에 담는다

answer += 담을때 가장 싼 가격 * m

function solution(k, m, score) {
    var answer = 0;
    score.sort((a, b) => b - a);
    while(score.length >= m) {
        const box = score.splice(0, m);
        const cheapest = box[m-1];
        answer += cheapest * m;
    }
    return answer;
}

=> 시간초과: sort 워스트는 O(n^2) 이기 때문에 (10^6)^2 >10^8

=> 그럼 obj O(n) 사용

큰 수 k 부터 하나씩 줄여가며, 카운트가 m개가 됬을때 

---

<2번째>

function solution(k, m, score) {
    var answer = 0;
    const obj = {};
    // O(n)
    for (const s of score) {
        obj[s] = (obj[s] || 0) + 1;
    }
    let count = 0;
    const minScore = Math.min(...score);
    
    for (let currScore = k; currScore > 0; currScore--) {
        // 현재점수의 사과가 없으면 패스
        if (!obj[currScore]) {
            continue;
        }
        const currScoreAppleCount = obj[currScore]; // 각 점수의 사과 갯수
        
        // 현재점수의 사과가 있다
        count += currScoreAppleCount;
        
        // 그러나 마지막 점수이고, 사과가 부족하다
        if (currScore === minScore && count < m) {
            break;
        }
        // 있는만큼 더해준다
        answer += currScore * m * Math.floor(count / m);
        // 남은 갯수를 다음 상자로 내려보낸다
        count = count % m;
    }
    return answer;
}

=> 런타임에러

 

시간초과 vs 런타임

시간초과는 제한시간 동안 프로그램이 안 끝난 거

• 무한반복
• 시간복잡도 큰 경우

런타임 에러는 컴파일성공하고 프로그램 실행중 에러 발생

• 배열의 범위 밖을 참조 (index 넘어감)
• 초기화를 안 해줘서 잔재가 남았을 경우
• 0으로 나눌때
• 재귀 함수 호출이 너무 깊어 스택오버플로우 일때

---

<3번째>

=> 아무리 봐도 위의 경우들로 생기는 문제가 아니여서 한줄씩 return 0을 써서 일부러 에러를 내보고, 그랬는데도 런타임에러가 나오는 곳을 찾아봤다.

아니 왠걸 const minScore = Math.min(...score) 에서 런타임에러가 생기는걸 발견

그렇다 10^7이상이면 Math.min 자체에서 오류가 난다.

 

 // const minScore = Math.min(...score); // !!!!!!! 10^7 => Math.min 사용하면 안돼!
let minScore = score[0];
for (const s of score) {
    if (minScore > s) {
        minScore = s;
    }
}

이렇게 수동적으로 minScore을 계산해주니 통과했다. 두시간 찾아 해맨 원인이 js자체 메서드였다늬..

 

오늘의 레슨

• 제한사항에 10^7이 있으면 Math.min, max는 쓰지말자
• 런타임에러가 어디서 나오는지 모르겠으면, 한 줄씩 일부러 에러를 내는 코드를 작성해보고, 그래도 런타임에러가 생기면 바로 그곳이 오류의 단서!