[프로그래머스] 체육복 - 자바스크립트(JavaScript)

문제 파악

 프로그래머스 그리디 유형의 문제 중 하나인 체육복 문제를 풀어보았다. 그리디 알고리즘에 관한 문제는 문제 파악이 중요하다. 우선 문제부터 보자.

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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번부터 순서대로 따져볼 나의 풀이법에서는 고려해야할 부분이 있었다. 몇가지 테스트 케이스가 자꾸 실패해서 찾아보다가 발견했는데 배열에 담긴 숫자가 오름차순으로 정렬되어있지 않았다는 점이다. 이것은 인지하지 못했다면 문제를 못 풀었을 것이다.

풀이 과정

1. 입력 데이터 오름차순 정렬

 오름차순 정렬과 관련하여 sort()에 대해 다룬 적이 있다. 바로 적용해주자.

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

2. 현재 체육복 보유 상태 정리

 체육복 여벌은 없지만 도난 당하지 않은 학생과 여벌의 체육복이 있는데 도난당한 학생은 결국 같은 상태이다. 이 두 케이스를 하나로 생각하면 체육복 보유 상태 경우의 수는 체육복 0개, 1개, 2개와 같이 3가지로 줄어든다. 이 과정을 통해 구현이 많이 간단해진다.

 lost와 reserve 두 배열에 공통적으로 담겨진 번호의 학생을 처리해주자. 각 배열에서 해당 번호만 제거하면 된다. 해당 배열의 원소를 제거하는 작업이라서 tmp라는 임시 배열에 중복되는 번호를 모은 뒤 각 배열에서 해당 원소를 제거해주었다. 그렇지 않으면 순회하는 배열의 원소를 건드리는 작업이 되어서 더 복잡해진다. 다른 방법이 있겠지만 직관적이고 메모리를 줄여야할 상황도 아니기에 이 방법을 채택하였다. 다른 사람들이 보기에도 좋은것 같다

// 중복되어 담겨진 번호 리스트 구하기
let tmp = [];
lost.forEach(v => {
    if (reserve.includes(v)) {
        tmp.push(v)
    }
})

// 각 배열에 중복되어 담겨진 번호 제거
tmp.forEach(v => {
    lost.splice(lost.indexOf(v), 1)
    reserve.splice(reserve.indexOf(v), 1)
})

3. 체육복 교환하기

 체육복 교환을 따져볼 준비가 모두 되었다. 체육복 교환을 어떻게 구현할지 생각해보자.

 우선 체육복 교환전 체육 수업 참여가 가능한 학생 수(answer)는 n - lost.length이다. 그리고 lost 배열에 담긴 학생들의 번호를 순회하며 해당 번호 앞과 뒤 학생의 체육복 여벌이 있는지 살펴본다. 만약 있다면 reserver에서 빌려준 학생의 번호를 제거해나가면 된다. 빌려주는 행위가 발생하면, 즉 reserve 배열의 요소가 삭제될 때 answer는 1씩 증가한다.

 참고로 자바스크립트에서 배열의 원소 제거는 splice를 이용하여 할 수 있다.

let arr = [1, 2, 3, 4, 5];

// 값이 3인 원소 제거하기
arr.splice(arr.indexOf(3), 1);

 

내가 코드로 구현한 것은 다음과 같다.

// 체육복 교환 전 상태 (변수 answer 초기화)
let answer = n - lost.length;
    
// 그리디 : 체육복 교환하기
lost.forEach(v => {
    if (reserve.includes(v - 1)) {
    	// 앞 번호 학생에게 체육복 여벌이 있을 시
        reserve.splice(reserve.indexOf(v - 1), 1);
        answer++;
    } else if (reserve.includes(v + 1)) {
        // 뒷 번호 학생에게 체육복 여벌이 있을 시
        reserve.splice(reserve.indexOf(v + 1), 1);
        answer++;
    }
})

최종 풀이

function solution(n, lost, reserve) {
    // 입력 데이터 오름차순 정렬
    lost.sort((a, b) => a - b);
    reserve.sort((a, b) => a - b);
    
    // 현재 체육복 보유 상태 정리 = 여유 있는데 도난 당한 학생 체육복 처리
    let tmp = [];
    lost.forEach(v => {
        if (reserve.includes(v)) {
            tmp.push(v)
        }
    })
    tmp.forEach(v => {
        lost.splice(lost.indexOf(v), 1)
        reserve.splice(reserve.indexOf(v), 1)
    })
    
    // 변수 초기화 : 체육복 교환 전 상태
    let answer = n - lost.length;
    
    // 그리디 : 체육복 교환하기
    lost.forEach(v => {
        if (reserve.includes(v - 1)) {
            reserve.splice(reserve.indexOf(v - 1), 1);
            answer++;
        } else if (reserve.includes(v + 1)) {
            reserve.splice(reserve.indexOf(v + 1), 1);
            answer++;
        }
    })
    
    return answer;
}

후기

 코딩 문제를 풀어본 경험이 없다는게 확 티가 날 만큼 부족했다. 사소한 실수들이 겹쳐지다보니 해답으로 가는 길이 더 멀게만 느껴졌다. 자꾸 경험하면서 노하우가 쌓이다보면 사소한 문제로 발목잡히는 경우가 줄어들 것이라 믿는다. 이 문제를 풀면서 내 풀이의 문제점과 오류들을 발견해서 어떤 것인지 정의한 뒤 하나씩 해결하다보니 해답을 찾았다. 이런 과정을 반복하는 것이 성장으로 이어지겠지? 아무튼 체육복 도둑 빨리 잡길 ^^