프로그래머스 [Lv. 2] 완전범죄 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(info, n, m) {
    let answer = 0;
    const lenI = info.length;
    info.sort(([a, b], [c, d]) => c/d - a/b);
    let [cntA, cntB] = [0, 0];
    for (let i = 0; i < lenI; i++) {
        const [showA, showB] = info.at(i);
        if (cntB + showB < m) {
            cntB += showB;
        } else {
            cntA += showA;
        }
    }
    if (cntA >= n) {
        answer = -1;
    } else {
        answer = cntA;
    }
    
    return answer;
}

풀이 방법

1. A에게 부담이 되는 흔적부터 정렬한다.
   1. 여기서 A에게 부담이 되는 흔적이란 무작정 흔적의 개수가 많은 것을 의미하지 않는다.
   2. 예를 들어 [2, 3]과 [1, 1]이 있다면 A에게 부담이 되는 것은 [1, 1]이 된다.
   3. 왜냐하면 B가 3의 흔적을 남기면 A의 흔적 2개를 지우는 것이지만
   4. B가 [1, 1]씩 3번 흔적을 남기면 A의 흔적 3개를 지울 수 있다.
   5. 따라서 [a흔적, b흔적] 을 a흔적을 b흔적으로 나눈 값이 큰 순으로 정렬한다.
2. 정렬된 값을 B의 최대 수용량만큼 채운다.
3. 나머지는 A에 채운다.
4. A가 n 이상이면 answer = -1
5. 아니라면 A의 흔적만큼 반환하면 끝!

느낀점

• 처음엔 마냥 A에게 많은 흔적이 되는 것 부터 지웠다.
• 오랜만에 프로그래머스 lv2문제들이 올라와서 남김없이 풀어보려고 한다.
• 시간복잡도를 계산하지 않았다면 이걸 dfs로 풀었을 것 같다.
  • dfs로 접근하게 된다면 흔적을 남길지 지울지 하는 선택지 2개
  • 총 info의 길이 40개
  • 2^40 = 1,099,511,627,776
  • 이렇게 되면 시간초과를 해결할 수 없다.