체육복

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

문제에서 제시하는 매개변수는 다음과 같았다.

 

• n =>현재 전체 학생 수
• lost =>체육복 없는 학생의 번호
• reserve => 여벌의 체육복 번호

reserve는 숫자가 담긴 배열인데, 1만큼 더하고,뺀 번호가 lost에 있으면 그 학생에게 체육복을 빌려줄 수 있다.

처음에는 별도의 배열을 담아서 reserve에 존재하는 숫자를 1만큼 더하고 뺀 값을 만들었지만, 해당 배열은 빌려준 체육복을 빼기가 힘들다는 점이 있었다.

 

function solution(n, lost, reserve) {
    let currentStudent = n - lost.length;
    let available = [...new Set(reserve.flatMap(num => [num - 1, num + 1]))];

    lost.forEach((student) => {
        if (available.includes(student)) {
            currentStudent++; 
            available = available.filter(num => num !== student); 
        }
    });

    console.log(currentStudent);
    return currentStudent;
}

 

그래도 flatMap 메서드와 Set 메서드로 중복 제거를 할 수 있는 경험은 했다.

그래서 별도의 배열 생성 없이 바로 1대1로 비교하여 lost,reserver를 비교하도록했다.

 

그런데도 테스트케이스에서 계속 문제가 발생했다.

 

function solution(n, lost, reserve) {
  // 본인의 여벌 체육복이 도난당한 경우 제거
  let filteredLost = lost.filter(student => !reserve.includes(student)).sort((a, b) => a - b);
  let filteredReserve = reserve.filter(student => !lost.includes(student)).sort((a, b) => a - b);

  // reserve에 있는 학생들을 순회하며 빌려줄 수 있는 lost 학생을 찾아 제거
  for (let r of filteredReserve) {
    const idx = filteredLost.findIndex(l => l === r - 1 || l === r + 1);
    if (idx !== -1) {
      filteredLost.splice(idx, 1);
    }
  }
  
  // 최종적으로 빌리지 못한 학생들의 수를 빼서 계산
  return n - filteredLost.length;
}

 

 

GPT가 제시한 코드이다. 설명은 다음과 같다.

 

코드 설명

중복 학생 제거 (자기 체육복 + 여벌 체육복이 있는 학생 처리) 문제 상황: 어떤 학생은 원래 체육복을 잃어버렸지만, 동시에 여벌 체육복도 가지고 있을 수 있어. 해결: filteredLost는 원래 잃어버린 학생들(lost) 중에서 여벌이 있는 학생을 제외하고 정렬한다. filteredReserve는 여벌 체육복을 가진 학생들(reserve) 중에서 원래 체육복을 잃어버린 학생을 제외하고 정렬한다.

이유: 이 과정을 통해, 본인의 체육복이 도난당했더라도 실제로 다른 학생에게 빌려줄 여벌 체육복이 있는 학생만 남기게 된다. 배열 정렬 sort((a, b) => a - b)를 사용하여 숫자 순서대로 정렬하면, 번호가 작은 학생부터 순차적으로 처리할 수 있다.

장점: 순서대로 처리하면, 예를 들어 번호 3의 학생이 체육복을 빌려줄 수 있다면, 번호 2나 4 중 먼저 빌려줘야 할 학생을 정확하게 판단할 수 있다.

체육복 빌려주기 (1대1 매칭) for ... of 루프로 여벌 체육복이 있는 각 학생 r에 대해, filteredLost.findIndex(l => l === r - 1 || l === r + 1)를 사용하여, r의 바로 앞(r - 1)이나 바로 뒤(r + 1)에 해당하는 학생이 잃어버린 목록에 있는지 검사한다. 빌려주면: 조건을 만족하는 학생을 찾으면(findIndex가 -1이 아니라면), 그 학생은 체육복을 빌릴 수 있으므로 배열에서 제거(splice)하여 다시 빌려주지 않도록 한다. 최종 계산 체육복을 빌리지 못한 학생들은 filteredLost에 남아 있다.

따라서, 전체 학생 수 n에서 남은 filteredLost.length를 빼면, 체육수업에 참여할 수 있는 최대 학생 수가 나온다.



요약

중복 제거: 본인 체육복 + 여벌 체육복을 가진 학생은 다른 사람에게 빌려줄 수 없으므로 두 배열에서 제거함.

정렬: 번호 순으로 정렬하여 순차적으로 매칭이 이루어지게 함.

매칭: 각 여벌 체육복 학생이 자신의 바로 옆 번호(앞 혹은 뒤)의 학생과 1대1로 매칭되어 체육복을 빌려줌. 최종 결과: 전체 학생 수에서 체육복을 빌리지 못한 학생 수를 뺀 값이 답이 됨.

 

...그리디 탐색 문제 위주로 풀고 있는데 최적해를 찾는 문제들이다 보니 테스트케이스가 추가된 문제들이나 신경 쓰지 못한 테스트케이스들이 많은 것 같다.

다음에는 다른 알고리즘 종류를 찾아 풀어봐야겠다.