[프로그래머스] 체육복 (lv.1 그리디)

🟠 문제

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

프로그래머스

 

🟠 첫번째 풀이

아무것도 고려하지 않은 채 if 문을 갈겨서 문제를 풀었더니 3, 5, 7, 12, 24 다섯 개의 테스트케이스에서 틀렸다 ㅎ헤헤헤 문제 보자마자 그냥 if문을 갈겼는데! 역시나 뭐 하나 생각이 빠진 것 같다.

가장 먼저 생각했던것은, 그냥 입력받은 전체 학생수를 기준으로, lost에 존재하는데 옷을 빌려줄 사람이 없다면 -1 해주는 방식으로 진행했다.

❌ 틀린 코드

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    var total = n
    var reserve = reserve

    for num in 1...n {
        if lost.contains(num) {
            if reserve.contains(num-1) {
                reserve.remove(at: reserve.firstIndex(of: num-1)!)
            } else if reserve.contains(num+1) {
                reserve.remove(at: reserve.firstIndex(of: num+1)!)
            } else {
                total -= 1
            }
        }
    }
    return total
}

 

❌ 5번 12번 테케 틀림!! 

아,, 조건하나를 빼먹었다. 체육복 여벌을 가진 친구가 체육복을 도둑맞았을 경우, 본인이 그걸 입어야해서 더이상 reserve 배열에 남아있을 수 없다. 이부분을 체크해주지 않았다. 바로 구현 고 했지만? 틀렸고요?

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    var total = n
    var lost = lost
    var reserve = reserve

    for num in 1...n {
        if lost.contains(num), reserve.contains(num) {
            lost.remove(at: lost.firstIndex(of: num)!)
            reserve.remove(at: reserve.firstIndex(of: num)!)
            continue
        }

        if lost.contains(num) {
            if reserve.contains(num-1) {
                reserve.remove(at: reserve.firstIndex(of: num-1)!)
            } else if reserve.contains(num+1) {
                reserve.remove(at: reserve.firstIndex(of: num+1)!)
            } else {
                total -= 1
            }
        }
    }
    return total
}

 

✅ 자, 세번째 시도

뭐가 틀려!!!!!!! 
일단, 같은 애들을 하나의 for문 내부에서 돌리게되면 lost 가 ㄱㅖ속 변형되고, 검토하지 않아도 될 lost애들이 조건문을 통과하게 된다. 그래서 하나의 for문을 두개로 분리해서 작성해야했다. 즉

1. lost한 애들이 reserve에 있으면 제거해주는 작업이 선행되고
2. 그다음 lost 애들이 체육복을 빌릴 수 있는 지 확인해야함

이순서대로 가야했다. 그래도 계속 13번과 14번 테스트케이스가 틀렸다 ㅋㅋㅋㅋ 아오빡쳐! 왜틀리지 

아래 예외사항을 찾았다.... for 루프는 순서대로 돌아가게 되어있다. 만약, 입력받는 수들이 정렬되어 있지 않은 상태로 들어오게 되면, 옷을 최대로 빌려줄수 없게 된다.  (아래 필기를 보자)

이런 경우가 생긴다. lost를 [2, 4]로 정렬하면, 3번이 2에게 빌려주고, 5번이 4에게 빌려줄 수 있을 것이다. lost를 탐색할 때 4먼저 탐색하고, reserve에서 3을 먼저 꺼내와서 최대 인원을 구하지 못했다. 이 문제를 해결해주기 위해서는 간단하게 lost 와 reserve를 오름차순으로 정렬해주면 된다.  휴 💨

 

🟠 정답코드

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    var total = n
    var lost = lost.sorted(by: <)
    var reserve = reserve.sorted(by: <)

    for num in lost {
        if reserve.contains(num) {
            reserve.remove(at: reserve.firstIndex(of: num)!)
            lost.remove(at: lost.firstIndex(of: num)!)
        }
    }

    for l in lost {
        if reserve.contains(l-1) {
            reserve.remove(at: reserve.firstIndex(of: l-1)!)
        } else if reserve.contains(l+1) {
            reserve.remove(at: reserve.firstIndex(of: l+1)!)
        } else {
            total -= 1
        }
    }

    return total
}