프로그래머스 - 체육복

1. 문제

문제 링크

설명

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

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

제한사항

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

2. 풀이

2-1. 조건

1. 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있다.
2. 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있다.

2-2. 풀이

제가 풀이한 방식은 이러합니다.
맨 처음에 체육복을 잃어버린 학생이 몇 명인지 세고
여벌의 체육복을 가져온 학생들이 빌려주는 부분에서
잃어버린 학생의 수를 감소시키는 방식입니다.

말로만 하면 뭔 말인지 모르겠으니 차근차근 구현해봅시다.

계획1 - 전체 학생을 초기화합니다.

const wear = [...Array(n + 2)].map(() => 1);

현실의 복잡한 문제를 컴퓨터 데이터화 하기 위해 제가 선택한 자료구조는 1차원 배열입니다.
기본적으로 학생들은 체육복 한 벌씩은 있으니까 1로 초기화를 합니다.
그리고 앞, 뒤 학생에게 빌려주는 부분을 구현할 때 인덱스를 벗어나기 때문에
n + 2로 길이를 초기화 했습니다.

계획2 - 여벌의 옷이 있는 학생들과 옷을 잃어버린 학생들이 몇 명인지 초기화합니다.

let lost_cnt = 0; // 옷을 잃어버린 학생 수

reserve.forEach(v => wear[v]++); // 여별의 옷을 가져온 학생들
lost.forEach(v => {
    wear[v]--;
    if (!wear[v]) lost_cnt++; // 옷이 없다면 잃어버린 학생 수 변수 증가
});

이런 식으로 구현하면 2-1에서 정리한 2번 조건을 신경 안쓰고
총 몇 명이 옷이 없는지, 어떤 학생이 옷을 빌려줄 수 있는지 알 수 있습니다.

계획3 - 옷을 빌려줍니다.

 reserve.forEach(v => {
   	// 옷을 빌려줄 수 있을 때 (2벌 이상 있을 때)
        if (wear[v] >= 2) {
            if (!wear[v - 1]) { // 앞자리 학생이 옷이 없을 때
                wear[v - 1]++;
                wear[v]--;
                lost_cnt--;
            }
            else if (!wear[v + 1]) { // 뒷자리 학생이 옷이 없을 때
                wear[v + 1]++;
                wear[v]--;
                lost_cnt--;
            }
	}
});

이런 식으로 옷을 빌려줄 수 있으면 빌려주고
빌려줄 때마다 잃어버린 학생 수 변수를 감소시킵니다.

계획4 - 전체 학생수에서 옷을 잃어버린 학생 수를 리턴합니다.

이 뜻은 옷이 있는 학생 수를 리턴하겠다와 동일한 말이겠죠?

3. 전체 코드

function solution(n, lost, reserve) {
    // 계획1 - 전체 학생을 초기화합니다.
    const wear = [...Array(n + 2)].map(() => 1);
    
    // 계획2 - 여벌의 옷이 있는 학생들과 옷을 잃어버린 학생들이 몇 명인지 초기화합니다.
    let lost_cnt = 0; // 옷을 잃어버린 학생 수

    reserve.forEach(v => wear[v]++); // 여별의 옷을 가져온 학생들
    lost.forEach(v => {
        wear[v]--;
        if (!wear[v]) lost_cnt++; // 옷이 없다면 잃어버린 학생 수 변수 증가
    });

    // 계획3 - 옷을 빌려줍니다.
    reserve.forEach(v => {
        // 옷을 빌려줄 수 있을 때 (2벌 이상 있을 때)
        if (wear[v] >= 2) {
            if (!wear[v - 1]) { // 앞자리 학생이 옷이 없을 때
                wear[v - 1]++;
                wear[v]--;
                lost_cnt--;
            }
            else if (!wear[v + 1]) { // 뒷자리 학생이 옷이 없을 때
                wear[v + 1]++;
                wear[v]--;
                lost_cnt--;
            }
        }
    });

    // 계획4 - 전체 학생수에서 옷을 잃어버린 학생 수를 리턴합니다.
    return n - lost_cnt;
}