[프로그래머스 Lv.1] 체육복 JavaScript 풀이

문제

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

 

입출력 예

 

 

풀이

접근 및 풀이

처음에 도난 당했으면서 여벌 있는 학생을 처리해준다.

그 후 체육복을 "최대한" 많은 학생이 수업을 들을 수 있도록 넘겨주면 된다.

여기서 여러가지 접근법을 생각해보았는데,

+-1일 때 체육복을 전달해주는 것을 기본으로 하되 "최대한" 많은 학생이 받도록 하는 것이 포인트다.

 

1. 한쪽 방향으로 넘겨주기.

오른쪽에 없는 사람이 있으면 쭉 넘겨주고,

다시 돌아오면서 왼쪽에 없는 사람이 있으면 쭉 넘겨준다.

그러나 이 경우에 아래와 같은 case를 처리하지 못한다고 판단하였다.

(사진추가)

 

2. possible 변수 도입

따라서 possible이라는 변수를 도입해서 이를 해결해주려고 하였다.

lost에 있는 사람이 양 옆에 있는 사람에게 받을 수 있는 경우 예외처리가 필요하다고 생각하였다.

따라서 possible이 1인 경우에 우선권을 주어 체육복을 빌려주고

2일 경우에는 우선 넘기는 방법을 채택하였다.

 

 

코드

function solution(n, lost, reserve) {
    var answer = 0;
    let new_lost = []
    
    //도난 당했으면서 여벌 있는 학생 처리
    for (let i=0; i<lost.length; i++) {
        let flag = false;
        for (let j =0; j<reserve.length; j++) {
            if (lost[i] === reserve[j]) {
                flag = true;
                reserve.splice(j, 1);
                break;
            }
        }
        if (!flag) {
            new_lost.push(lost[i]);
        }
    }
    
    lost = new_lost;
    new_lost = [];
    
    //한 번 돌리기
    for (let i = 0; i < lost.length; i++) {
        let left = lost[i] -1;
        let right = lost[i] +1;
        let possible = 0;        
        let idx = [];
        
        for (let j = 0; j < reserve.length; j++) {
            let number = reserve[j];
            if ((left === number) || (right===number)) {
                possible ++;
                idx.push(j);
            }
        }
        if (possible === 2 ) { continue; }
        else if ( possible === 1) { reserve.splice(idx[0], 1)}
        else if ( possible === 0) { new_lost.push(lost[i])}
        else { conosle.log('possible에 오류가 있습니다.')}
    }
    
    lost = new_lost;
    new_lost = [];
    answer = n - lost.length;
    
    return answer;
}

 

그러나 이 코드에는 문제가 있다!!!!!!!!

possible이 2일 때 우선 continue를 해주었는데 이렇게 하면

2명한테 받을 수 있으면 받았다고 치고 넘어가고 reserve에서도 삭제해주지 않음을 뜻한다.

이로 인해 발생할 수 있는 문제는 reserve에서 어떤 학생이 두명에게 체육복을 줄 수도 있다는 것이다.

다만 이를 만족하는 반례를 아직 찾지못했다...

 

사실 내 의도는 new_lost에 넣어준 후

뒤에서 한 번 더 리스트를 돌면서 처리해주려고 했다.

다만 이 문제를 너무 오래 붙잡고있어서 우선은 보내주기로 했다.

 

실력이 좀 더 늘면 무엇이 부족했는지,

혹은 구체적인 반례케이스가 있는지 알게될 것이라고 생각한다.