[프로그래머스(LV1)] 체육복

문제 설명

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

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

• 입출력 예

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

---

내가 작성한 코드

import Foundation

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    
    var count: Int = n - lost.count // 최소한의 값을 기본으로 초기화
    var reserve = reserve
    var lost = lost
    
    reserve = reserve.sorted{$0 < $1}
    lost = lost.sorted{$0 < $1}
    
    for i in reserve {
        if lost.contains(i){
            reserve.remove(at: reserve.firstIndex(of: i)!)
            lost.remove(at: lost.firstIndex(of: i)!)
            count += 1
        }
    }
    
    for i in lost {
        if reserve.contains(i - 1){
            count += 1
            reserve.remove(at: reserve.firstIndex(of: i - 1)!)
        } else if reserve.contains(i + 1) {
            count += 1
            reserve.remove(at: reserve.firstIndex(of: i + 1)!)
        } else {
            continue
        }
    }
    return count
}

일단 이 문제는 그리디 알고리즘 문제라고 한다. 아직까지 그리디 알고리즘에 대해 자세히 공부하지 못해 완벽하게는 알 지 못한다. 그래도 검색해본 결과로는 "탐욕적"인 알고리즘으로 눈 앞의 최선의 방법을 우선적으로 찾는 알고리즘이라고 한다. 거스름돈을 계산할 때 최소한의 개수로 거스름돈을 계산하는 방법이 대표적인 예라고 한다.

아무튼 코드를 설명해보자면 먼저 count라는 값에 학생 수 - lost 값으로 초기화하여 count에 1씩 더하며 결과를 찾는 쪽으로 구현해보았다.

처음에는 reserve와 lost를 정렬하지않고 제출했더니 13,14번이 실패가 떴었다. 검색하다 정렬이 문제라는 것을 알게되어 정렬 코드를 추가하니 통과됐다. 자리 인덱스로 구현한 것이 아닌 값 중심으로 구현을 했는데 정렬이 왜 필요한지 솔직히 잘 모르겠다.. 정렬없이 실패가 뜨는 테스트 케이스를 찾지 못했다ㅠ

reserve안의 값으로 for문을 돌려가며 만약 lost에도 있을 시엔 두 배열에서 모두 지워주도록했다. 이는 여벌이 있는 사람이 도둑맞았을 경우를 나타내는 코드이며, 이를 먼저 작성하지 않고 나중에 작성한다면 이미 2번이 3번에게 빌린 상태인데 3번이 도둑맞은 경우도 생기므로 오류가 발생하게 될 것이다.

이렇게 여벌이 있는 사람 중 도둑 맞은 사람을 제외한 뒤, 다시 lost안의 값으로 for문을 돌리며 reserve에 lost 해당 값에서 1이 차이나는 값들이 존재하는지 확인 후에 만약 존재한다면 count에 1을 더해주고 그렇지 않다면 다음 반복으로 진행되도록 하였다.

---

아직 이해가 안되는 부분들이 많은 것 같다. 더 노력해보자.