[LV1] 체육복

이제부터 코드블록에 주석을 써야 할 것 같다. 내 코드를 내가 분석하는 일이 생기고 있다...

문제 설명

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

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

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

입출력 예 설명

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

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

 

처음에 문제가 잘 이해되지 않아 한참을 읽어보았다. 

체육복을 모두 1개 또는 2개를 가지고 있는데, 이를 1개씩만 도난당해서 결국 체육복이 0, 1, 2개인 학생들이 존재하고 이중에서 체육복이 2개인 학생이 0개인 학생에게 빌려주어 최대한 많은 학생이 1개 또는 2개의 체육복을 가질 수 있게 하라는 문제였다. 

 

나는 lost와 reserve 두 배열의 값을 비교하여 만약 두 배열의 값이 위아래로 1씩 차이난다면 reserve 배열(체육복이 2개였다가 1개가 된 학생)과 lost 배열(체육복이 0개였다가 1개가 된 학생)의 값을 모두 지워주는 방식을 사용했다.

1. while문 선언
2. lost 배열이 reserve 배열의 (맨 처음 값 - 1) 또는 (맨 처음 값 + 1)을 포함한다면 reserve 배열의 첫 값을 삭제(shift() 이용) => reserve 배열의 첫 값을 번호로 가지는 학생이 1개의 체육복을 빌려주어 1명이 더 수업을 들을 수 있게 됨
3. lost 배열 내 reserve 배열의 (맨 처음 값 - 1) 또는 (맨 처음 값 + 1)을 ""로 변환. 
4. 만약 포함하지 않는다면 reserve 배열의 맨 첫값만 삭제 => 체육복을 빌려줄 수 있는 학생이 없음
5. reserve 배열의 길이가 0이 될 때 까지 반복
6. n에서 남은 lost 배열의 길이(체육복을 얻지 못한 학생 수)를 뺌

let i = 0
while (reserve.length > 0) {
//reserve가 빈 배열이 될 때 까지
    if (lost.includes(reserve[i] - 1)) {
    //lost가 reserve의 첫 값 -1 또는 +1을 가지면
        lost[lost.indexOf(reserve[i] - 1)] = ""
        //해당 값은 ""로 바꿈
        reserve.shift()
        //reserve 배열의 첫 값은 삭제
    } else if (lost.includes(reserve[i] + 1)) {
        lost[lost.indexOf(reserve[i] + 1)] = ""
        reserve.shift()
    } else {
    //가지고 있지 않다면
        reserve.shift()
        //reserve만 삭제
    }
}
answer = n - lost.filter(a=>a != "").length
//전체 학생에서 체육복이 없는 학생의 수를 빼줌

하지만 제대로 작동이 되지 않았다. 흠..

html로 간단하게 나타내 보았다

작동 원리는 다음과 같다. 다른 테스트 케이스를 입력해 보았을 때도 웬만하면 작동했지만 계속 오류가 나서 질문글에서 반례를 몇개 찾아보았다.

 

먼저 reserve가 [4, 2], lost가 [3, 5]인 경우. 

이론상이라면 2가 3에게, 4가 5에게 체육복을 빌려주면 모두가 체육 수업을 들을 수 있었는데, 이 케이스를 위 코드에 넣고 돌려보니

이와 같은 결과가 나왔다. 4가 먼저 3에게 체육복을 줘버리니 2와 5는 서로 체육복을 공유할 수 없게 되어 버린 것이었다.

생각보다 해결책은 간단했다. 바로 오름차순 정렬을 사용하는 것. 

reserve.sort((a,b) => a - b)

 

편안해졌다. 원리는 간단하다. 작은 수부터 계속 실행하다 보면 실행하는 수와 가장 큰 수와의 간격이 점점 좁아질 것이다. 그렇다면 위의 경우처럼 간격이 작은 수가 먼저 사라지는 불상사를 막을 수 있는 것이다.

 

두번째 경우는 바로 중복이 존재하는 경우이다. 

문제를 잘 읽어보면, 

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

이라는 조건이 있는데, 쉽게 말해 reserve에 속한 학생이 lost에도 속할 수 있다는 것이다.

reserve = [1,3,5,7], lost = [5, 7, 8]일 경우, 5와 7은 체육복이 2벌에서 1벌로 줄었을 뿐, 체육 수업은 받을 수 있다. 또한 체육복이 하나밖에 없어 남에게 빌려줄 수가 없다. 하지만 실행 결과는

다음과 같이 나온다. 체육복이 1벌 있어 수업을 받을 수 있는 5, 7이 모두 lost 배열에 그대로 남아있으며, 심지어 7은 1벌뿐인 체육복을 8에게 빌려주기까지 했다. 대인배인가?

이런 경우를 해결하기 위해선, 미리 중복 요소를 제거하고 갈 수 밖에 없다. 

while문을 이용하여 reserve의 n번째 요소와 같은 요소가 lost에 들어있을 경우, 두 배열 모두에서 지워주는 과정을 거쳤다. 

let j = 0
while (reserve.length > j) {
//reserve의 길이만큼 반복
    if (lost.includes(reserve[j])) {
    //lost가 j번째 요소를 포함하면
        lost[lost.indexOf(reserve[j])] = ""
        reserve[j] = ""
        //두 배열의 값을 모두 ""로 만들어줌
    }
    j++
}

중복을 미리 제거해주니 제대로 된 세상의 모습이다. 

전체 학생 중 lost에 포함된 학생, 즉, 체육복이 없는 학생만 수업을 들을 수 없으니 n에서 lost의 길이를 빼주면 끝.

lost 배열은 ""도 요소로 가지고 있어 length로 길이를 재면 ""를 포함한 길이가 나오니, filter()를 통해 ""를 지워주자

 

function solution(n, lost, reserve) {
    var answer = 0;
    let i = 0;
    reserve.sort((a, b) => a - b)
    let j = 0
    while (reserve.length > j) {
        if (lost.includes(reserve[j])) {
            lost[lost.indexOf(reserve[j])] = ""
            reserve[j] = ""
        }
        j++
    }
    while (reserve.length > 0) {
        if (lost.includes(reserve[i] - 1)) {
            lost[lost.indexOf(reserve[i] - 1)] = ""
            reserve.shift()
        } else if (lost.includes(reserve[i] + 1)) {
            lost[lost.indexOf(reserve[i] + 1)] = ""
            reserve.shift()
        } else {
            reserve.shift()
        }
    }
    answer = n - lost.filter(a => a != "").length
    return answer;
  }

이게 탐욕법, 쉽게 말해 눈에 보이는것 부터 해결하는 알고리즘이라고 한다. 아마 sort()를 이용해 reserve 배열을 가장 작은 수부터 시작하도록 정렬해주는게 이 탐욕법의 과정중 하나가 아니었을까.....