[1단계] 체육복

프로그래머스 코딩테스트 연습

문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

탐욕법이란?

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"
탐욕(greedy) 알고리즘은 각 단계마다 지금 당장 가장 좋은 방법만을 선택하여 부분의 최적해들의 집합이 곧 전체문제의 해답이 될 때 사용 할 수 있다.

해결과정

• 총 인원 수는 n명, 잃어버린 사람은 lost.count, 여벌의 옷을 가지고 있는 사람은 reserve.count가 되어 생각을 했다.
• 처음에 n - lost.count 를 해주어 여벌이 있든 없든 체육 수업에 참여할 수 있는 사람의 수를 구한 상태에서 여벌 옷 상태와 잃어버린 상태를 보고 점차. +1 을 해주는 것을 생각하였다.

하지만 이렇게 하니 제한사항에 대한 예외처리 제대로 되지 않아 41점 밖에 얻지 못하였다. 그래서 다른사람은 이 문제를 어떻게 해석하였는지 살짝 보았는데 나는 사람을 기준으로 했다면 체육복 수 을 기준으로 해서 푸는 방법을 보고 유레카를 외쳤다. 🤭

소스코드

var clothes = [Int](repeating: 1, count: n)
var cant = 0

처음에 길이가 n인 clothes 라는 배열에 1을 넣어 체육복을 도둑맞기 전의 기본적인 상태로 만들었다. 그리고 빌리지 못한 사람을 담을 cant 변수를 만들어주었다.

for i in lost {
    clothes[i-1] = 0
}
    
for i in reserve {
    clothes[i-1] +=  1
}

그 다음 lost와 reserve 배열을 통해 lost면 0으로, reserve이면 +1로 현재 인원별로 체육복 수량을 나타내주었다.

 for i in 0..<n {
        if clothes[i] == 0 {
            if i>0 && clothes[i-1] > 1 {
                clothes[i-1] = 1
                clothes[i] = 1
            }else if i<n-1 && clothes[i+1] > 1 {
                clothes[i+1] = 1
                clothes[i] = 1
            }else {
               cant += 1 
            }
        }
    }

만약 clothes 중에 0이 들어있다면 앞 뒤 번호에게 빌리거나 만약 없을 경우엔 빌리지 못한 경우엔 빌리지 못한 사람에 +1을 해준다.

 return n - cant

마지막에는 총 n명 중에 빌리지 못한 cant를 빼주어 리턴하면 된다.

느낀점

내 방식대로 해보다가 안되서 다른사람의 해답을 보고 풀었지만 어려워보인다고 포기하지 않고 풀어서 다행이다. 문제가 길수록 풀기가 무서워지는데 그걸 극복해내야겠다고 생각했다..