체육복

문제 링크

📩 문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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명이 체육수업을 들을 수 있습니다.

반례

입력값 〉 10, [1, 2, 3, 4, 5, 6], [1, 2, 3]
기댓값 〉 7

입력값 〉 10, [4, 7], [1, 6, 8]
기댓값 〉 9

입력값 〉 5, [2, 3], [3, 4]
기댓값 〉 4

입력값 〉 5, [3, 4], [4, 3]
기댓값 〉 5

순서가 정렬되지 않은 테스트 코드
입력값 〉 5, [4, 2], [3, 5]
기댓값 〉 5

제출 답안

function solution(n, lost, reserve) {

		// 여벌없이 분실한 학생
    let realLost = lost.filter(l => !reserve.includes(l)).sort((a, b) => a - b);
		// 분실없이 여벌이 있는 학생
    let realReserve = reserve.filter(r => !lost.includes(r)).sort((a, b) => a - b);
    
		// 체육복을 빌릴 수 있는 학생 수
    let answer = n - realLost.length;

    for (let i = 0; i < realLost.length; i++) {
        let lostNum = realLost[i];
      
        for (let j = 0; j < realReserve.length; j++) {
            let reserveNum = realReserve[j];
            if (reserveNum === lostNum - 1 || reserveNum === lostNum + 1) {
              answer += 1;
              realReserve[j] = -1; 
              break; 
            }
        }
      }

    return answer;
}

답안 설명

먼저 여벌없이 체육복을 분실한 학생의 번호를 담은 realLost와 분실없이 여벌 체육복을 가지고 있는 학생의 번호를 담은 realReserve 배열을 만들어주었다. 이때 answer은 체육 수업에 참여할 수 있는 학생 수의 최댓값이므로 우선 전체 인원에서 realLost의 길이만큼 빼준 값을 할당하였다.

그리고 반복문을 돌려 realLost의 요소보다 1크거나 1작은 값이 realReserve에 존재하면 answer의 값을 1 추가하고, realReserve에서 그 값을 제거하였다. 이걸 realLost의 수만큼 반복을 하고 최종적으로 answer 값을 리턴하였다.

질문하기 페이지에서 반례를 찾아서 테스트 케이스를 추가했음에도 불구하고 계속 테스트는 통과하지만 채점 결과에서 두가지 테스트를 통과하지 못하는 결과가 나왔다. 마지막으로 찾은 반례를 테스트케이스에 넣어보니 통과하지 않았는데, 알고보니 lost와 reserve의 순서가 오름차순 정렬이 안되어있을 때의 테스트를 통과하지 못하고 있었다. 제한사항에 lost나 reserve의 배열이 항상 오름차순으로 정렬되었다는 조건이 따로 없으므로 realLost와 realReserve를 sort()를 사용하여 오름차순 정렬을 해주었다. 그렇게 하니 최종 채점에서도 통과할 수 있었다.

다른 풀이

function solution(n, lost, reserve) {

		// 여벌없이 분실한 학생
    let realLost = lost.filter(l => !reserve.includes(l)).sort((a, b) => a - b);
		// 분실없이 여벌이 있는 학생
    let realReserve = reserve.filter(r => !lost.includes(r)).sort((a, b) => a - b);
    
		// 체육복을 빌릴 수 있는 학생 수
    let answer = n - realLost.length;

for (let i = 0; i < realLost.length; i++) {
        let lostNum = realLost[i];
        for (let j = 0; j < realReserve.length; j++) {
            let reserveNum = realReserve[j];
            if (reserveNum === lostNum - 1 || reserveNum === lostNum + 1) {
                answer += 1;
                realReserve[j] = -1; 
                break; 
            }
        }

    return answer;
}

제출 풀이와 같은 로직이지만 사용 함수나 방식에서의 차이가 있다. 제출 코드는 for문과 filter,includes 함수를 사용한 코드이고 새로운 코드는 중첩 for문으로 되어있다.

성능 측면에서 볼때, 일반적으로 중첩된 for문은 루프 내부에 또 다른 루프가 있기 때문에 시간 복잡도가 O(n*m)으로, 배열의 크기가 커질수록 성능상 좋지 않다. 하지만 배열의 크기가 최대 30으로 제한되어있으므로, 이 중첩 for문의 성능 저하는 실제로는 무시할 수 있을 정도로 작다.

includes와 filter 함수를 사용하는 방법은 코드가 더 직관적이고 이해하기 쉬운 장점이 있지만 includes는 내부적으로 배열을 순회하므로 O(n)의 시간 복잡도를 가지며, filter함수 또한 배열을 순회하므로 O(n)의 시간 복잡도를 가진다. 따라서 두 함수를 연달아 사용하는 것은 기본적으로 O(2n)의 시간 복잡도를 가지게 되며, 실제로는 중첩 for문보다 더 비효율적일 수 있다.

그러나 앞서 언급했듯이 배열의 크기가 작기 떄문에 이러한 차이는 실제 실행에서 유의미한 성능차이를 일으키지 않을 가능성이 높다. 코드의 가독성과 유지 보수 측면을 고려해서 includes와 filter를 사용한 방식을 선택했다.