체육복 (Greedy)

탐욕법(Greedy)는 당장에 최적인 것을 골라 답을 내는 방식이다.

문제를 해결하는 과정에서 순간마다 가장 좋아보이는 최적의 해만 선택하는 풀이 방법

문제 링크🔗

처음 풀이

정확도 60%의 풀이
그나마 통과가 가장 많이 나온 풀이다 😂

가장 작은 거 or 큰 것부터 따질 필요가 없을 것 같아서 정렬은 따로 해주지 않았고
순서도 따질 필요가 없을 것 같아 for-i문이 아닌 for-of문을 사용했다.

function solution(n, lost, reserve) {
    let answer = n - lost.length;
    let count = 0; // 빌려준 횟수
    
    for (let x of reserve) {
        if (count === lost.length) {
            answer+= count;
            return answer;
        }
        
        if (lost.includes(x + 1) || lost.includes(x - 1)) {
            count++;
            
            if (count === reserve.length) {
                 answer+= count;
                return answer;
            }
        }
    }

    return answer;
}

새 풀이

• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.

처음에 이 두 가지를 lost, reserve 두 배열 간에 중복되는 게 없다고 잘못 이해했다. 이게 아니라 각 배열에서 중복이 없는 것
=> 즉, lost와 reserve 간에 중복이 있을 수 있다가 맞다. (예: lost=[2,3] reserve=[1,2])

여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

바로 이 예외가 위의 예시에 해당했다.
2번 학생이 여벌을 가져왔는데 도난도 당한 것이다. (첫 번째 예외를 이해 못해서 이건 무슨 말인지 몰랐음..)

또한, lost와 reserve 배열이 정렬되어 있지 않으면 다음과 같은 상황이 발생한다.

n=5 lost=[4,2] reserve=[3,5] 이면 바른 return 값은 5인데
정렬하지 않으면 순서대로 배열을 순회하게 되어서 4번 학생은 3번에게 빌려주게 되고,
2번 학생은 결국 여분의 체육복을 받지 못해서 체육 수업에 참여할 수 없다. (이 때는 return 값이 4명이 된다)

히든 케이스가 많은 문제였다. 😏

참고 링크를 여기까지 읽고 다시 문제를 풀어보았다.

참고 링크의 코드와는 살짝 달리 조건을 빨리 따질 수 있는 부분은 위로 끌어올려 보았다.

다시 풀다가 2가지 걸리는 부분이 생겼다.

• realLost.forEach 안의 if (realReserve.length === 0) return 부분을 filter 직후로 끌어올렸더니 2군데 테스트 케이스 오류가 났다. 어떤 경우인지는 잘 모르겠고(테케 내용 보게 해줘요 프로그래머스..) forEach 안에 다시 넣으니 올바르게 동작했다. 히든 케이스가 있는 모양이다 😭
• forEach 안의 2번째 if문인 realReserve.includes(x + 1)을 그냥 if로 하지 않고 else if로 해야 올바르게 동작했다. 이유를 생각해보니 아마 한쪽이 해당 안 될 경우 바로 반대 쪽을 검사해야 하기 때문에 그런 듯 하다.

최종적으로 테케를 모두 통과한 코드이다.

function solution(n, lost, reserve) {
    let answer = n;
    
    // 중복 제외
    let realLost = lost.filter((l) => !reserve.includes(l));
    let realReserve = reserve.filter((r) => !lost.includes(r));
    
    // lost가 없으면 answer(n) 바로 반환
    if (realLost.length === 0) return answer;
    
    // (lost가 있는 경우) answer에서 lost 갯수 제외
    answer -= realLost.length;
    
    // 올바른 체육복 렌트를 위해 lost 정렬 (reserve는 include 여부를 따지므로 정렬 필요 x)
    realLost.sort((a, b) => a - b);
    
    realLost.forEach((x) => {
        if (realReserve.length === 0) return;
        
        if (realReserve.includes(x - 1)) {
            realReserve = realReserve.filter((r) => r !== (x - 1))
            answer ++;
        } else if (realReserve.includes(x + 1)) {
            realReserve = realReserve.filter((r) => r !== (x + 1))
            answer ++;
        }
    })
    
    return answer;
}

이렇게 탐욕법 문제를 풀어보았다. 원래는 거스름돈이나 회의실 잡기 등 반드시 sort로 작은 거 or 큰 것부터 차례대로 정렬한 후에 최소 값을 구하는 문제를 많이 봤는데 이번 체육복 문제는 좀 특이하게 느껴졌다. 예외가 많아서 재밌었던 문제