항해 10일차 (알고리즘)

Undong·2023년 4월 13일

항해구구

목록 보기

10/52

항해 10일차

또 알고리즘을 풀었다.

체육복이라는 문제에서 많은 어려움을 겪었다. 테스트 케이스는 정상적으로 코드가 실행되는데 제출할 때는 다른 테스트 케이스들이 실패가 나왔다.

성공하기 전 코드..

function solution(n, lost, reserve) {

    // 오름차순 정렬
    let newLost = lost.sort((a, b) => a - b) // 1, 5,6, 7,24
    let newReserve = reserve.sort((a, b) => a - b)
    // n = ?
    //  lost = [2,4,6,8,10] 
    //  reserve = [1,3,4,5,8,13]


    // 도난도 안 당하고, 하나 더 있지도 않은 애들  but 자기 껀 있음.
    // let rest = n - lost.length - reserve.length


    // 도난을 당했지만 여벌이 있어서 상관없는 애들
    // 즉, lost에도 있고 reserve에도 있는 애들
    // 얘네들을 어떻게 구하느냐...

    // lost를 기준으로 filter(reserve랑 같은애들)를 써서 같은 애들만 골라내면 (더 정확히 말하자면 lost - reserve를 해서 차집합을 해줘야 함)
    // 걔네가 결국에는 도난을 당했지만 여벌이 있는 애들을 의미함.

    // reserve도 마찬가지로 filter를 써서 lost에도 있고 reserve에도 있는 애들을 찾아내요.(정확히 말하자면 빼버리는 것.)


    // 리얼 평범한 체육복 한 개 있는 애들  = n이 전체 학생 수 - 찐lost.length - 찐reserve.length

    let realLost = newLost.filter((a) => !newReserve.includes(a))
    let realReserve = newReserve.filter((a) => !newLost.includes(a))

    let rest = n - realLost.length - realReserve.length

    // 이렇게 다 거른 후에 찐 lost랑 찐 reserve 로 요리를 해야 함.
    // 이미 한 번 받은 애는 더 못 받게 해야 함.
    // 5	[2, 4]	[3]	4



    // 7, [2, 4], [1, 3]
    let checkBox = []  // [2, ]
    for (let i = 0; i < realLost.length; i++) {
        for (let j = 0; j < realReserve.length; j++) {
            if (Math.abs(realLost[i] - realReserve[j]) === 1) {
                if (!checkBox.includes(realLost[i])) {
                    checkBox.push(realLost[i])
                }
            }
        }
    }
    return rest + checkBox.length + realReserve.length
}

왜 안되지 ??? 이 알고리즘 한 문제에 3 ~ 4시간을 쓴 거 같다. 조원들과 머리를 맞대고 푼 결과

 if (!checkBox.includes(realLost[i])) {
                    checkBox.push(realLost[i])

위 코드가 이상하다는 것을 느꼈다..
이 코드는 realLost 배열의 요소가 이미 checkBox 배열에 포함되어 있지 않은 경우에만 해당 요소를 checkBox 배열에 추가하는 작업을 수행한다. 즉, realLost 배열에서 가져온 요소를 checkBox 배열에 중복되지 않게 추가하는 것이다.

checkBox 배열에 포함되지 않을 경우 realLost[ i ]를 추가 해주면 realReserve[j] 값도 저장해야 된다는 것을 깨달았다. 그 후 &&연산자와 새로운 배열 giveBox를 이용하여 수정하였다.

수정된 코드

function solution(n, lost, reserve) {
    let newLost = lost.sort((a, b) => a - b) 
    let newReserve = reserve.sort((a, b) => a - b)
    let realLost = newLost.filter((a) => !newReserve.includes(a))
    let realReserve = newReserve.filter((a) => !newLost.includes(a))
    let rest = n - realLost.length - realReserve.length
    let checkBox = []  
    let giveBox = [] // 새로운 배열 추가 
    for (let i = 0; i < realLost.length; i++) {
        for (let j = 0; j < realReserve.length; j++) {
            if (Math.abs(realLost[i] - realReserve[j]) === 1) {
                if (!checkBox.includes(realLost[i]) &&!giveBox.includes(realReserve[j])) { // 추가 
                    checkBox.push(realLost[i])
                    giveBox.push(realReserve[j])
                }
            }
        }
    }
    return rest + checkBox.length + realReserve.length
}