[프로그래머스 LV.1] #32 체육복 (JavaScript)

💡 문제

체육복

 

🔍 분석 및 계획

✅ 문제 이해

체육복을 도난당한 학생에게 여벌의 체육복이 있는 학생이 빌려주어 체육수업을 들을 수 있는 학생의 최대값을 구하기

• 입력 값 : 전체 학생수 n, 체육복을 도난당한 학생 배열 lost, 여벌이 있는 학생 배열 reserve
  - 2 <= n <= 30
  - 1 <= lost의 길이 <= n, 중복되는 번호는 없다
  - 1 <= reverse의 길이 <= n, 중복되는 번호는 없다
  - 여벌이 있는 학생은 앞뒤번호의 학생에게만 빌려줄 수 있다 (예 - 3번 => 2,4번)
  - 여벌이 있는 학생이 체육복을 도난당했을 시 다른 학생에게 빌려줄수 없다
• 출력 값 : 체육수업을 들을 수 있는 학생의 최대값

문제를 보며 떠오른 풀이는 lost와 reverse 배열 값을 키값으로 각각의 객체를 생성해 lost객체를 순회해가며 빌릴수 있을 시 객체에서 제거해가는 방법이다.

 

풀이순서

1. lost, reserve 배열값을 키값으로 가지는 lostMap, reserveMap객체 생성 -> O(n)
2. lostMap객체를 반복문으로 순회하며 해당 번호의 학생에게 빌려줄수 있는 학생을 reserverMap에서 찾을 시 양쪽에서 삭제 -> O(n)
3. 전체 인원에서 lostMap의 길이를 빼준값을 반환한다 - O(1)

 

 

✅ 의사코드 작성

 

//lost,reverse배열값을 키값으로 가지는 Map객체 생성
//lostMap객체를 반복문으로 순회
  //reverseMap에서 찾을 시 양쪽에서 삭제 => lost에서만 뺀다
// 전체 인원에서 lostMap길이를 빼준다

 

 

📝 코드 구현

의사코드 + 코드

수정사항

1. lost는 객체를 생성하지 않고 reserve만 생성한다.
   - 객체를 생성하면 함수처리하기가 더 복잡하고, 그냥 빌려줄수 있는 횟수를 담는 변수를 하나 생성하는 것이 더 간단하다
2. reserveMap에서만 삭제하고 삭제한 횟수를 변수에 카운트 해준다

function solution(n, lost, reserve) {
  //lost,reverse배열값을 키값으로 가지는 Map객체 생성
  const reserveMap = new Map();
  reserve.forEach((v) => {
    reserveMap.set(v, true);
  });
  //lostMap객체를 반복문으로 순회
  let cnt = 0;
  for (let i = 0; i < lost.length; i++) {
    //reverseMap에서 찾을 시 양쪽에서 삭제 => lost에서만 뺀다
    if (reserveMap.has(lost[i])) {
      reserveMap.delete(lost[i]);
      cnt++;
    } else if (reserveMap.has(lost[i] - 1)) {
      reserveMap.delete(lost[i] - 1);
      cnt++;
    } else if (reserveMap.has(lost[i] + 1)) {
      reserveMap.delete(lost[i] + 1);
      cnt++;
    }
  }
  // 전체 인원에서 lostMap길이를 빼준다
  return n - lost.length + cnt
}

 

최종 코드

1. 반복문내 코드 정리

function solution(n, lost, reserve) {
  const reserveMap = new Map();
  reserve.forEach((v) => {
    reserveMap.set(v, true);
  });
  let borrowed = 0;
  for (let i = 0; i < lost.length; i++) {
    if (!reserveMap.has(lost[i]) && !reserveMap.has(lost[i] - 1) && !reserveMap.has(lost[i] + 1)) continue;
    if (reserveMap.has(lost[i])) reserveMap.delete(lost[i]);
    else if (reserveMap.has(lost[i] - 1)) reserveMap.delete(lost[i] - 1);
    else if (reserveMap.has(lost[i] + 1)) reserveMap.delete(lost[i] + 1);
    borrowed++;
  }
  return n - lost.length + borrowed;
}

문제점

1. 정렬되지 않은 lost배열 입력 시  => 12,13번 예시 미통과

2. 여벌있는 학생이 도난당했을 시 빌려 줄수 없는데 앞번호 학생이 빌리려는 경우 => 5, 12번 예시 미통과

위 코드로는 두가지 예외 사항을 거르지 못해 문제가 발생

 

최종 코드

1. sort 함수로 lost배열을 오름차순 정렬

2. 뒷번호 학생의 여벌옷을 빌릴 시 그 학생도 도난당했는지 여부 확인하는 조건 넣어주기

function solution(n, lost, reserve) {
  const reserveMap = new Map();
  reserve.forEach((v) => {
    reserveMap.set(v, true);
  });
  lost.sort((a, b) => a - b);
  let borrowed = 0;
  for (let i = 0; i < lost.length; i++) {
    if (!reserveMap.has(lost[i]) && !reserveMap.has(lost[i] - 1) && !(reserveMap.has(lost[i] + 1) && !lost.includes(lost[i] + 1))) continue;
    if (reserveMap.has(lost[i])) reserveMap.delete(lost[i]);
    else if (reserveMap.has(lost[i] - 1)) reserveMap.delete(lost[i] - 1);
    else if (reserveMap.has(lost[i] + 1) && !lost.includes(lost[i] + 1)) reserveMap.delete(lost[i] + 1);
    borrowed++;
  }
  return n - lost.length + borrowed;
}

 

 

시간 복잡도 : O(nlogn)

 

💭 되돌아 보기

✅ 다른 사람 풀이

 

1.
추가 공간을 사용하지 않고 배열의 인덱스를 이용해 푼 문제. 이해하기도 쉽고 시간복잡도도 O(n)을 가지는 좋은라고 생각한다

function solution(n, lost, reserve) {
    const students = {};
    let answer = 0;
    for(let i = 1; i <= n; i++){
        students[i] = 1;
    }
    lost.forEach(number => students[number] -= 1);
    reserve.forEach(number => students[number] += 1);

    for(let i = 1; i <= n; i++){
        if(students[i] === 2 && students[i-1] === 0){
                students[i-1]++;
                students[i]--;
        } else if(students[i] === 2 && students[i+1] === 0){
                students[i+1]++;
                students[i]--;
        }
    }
    for(let key in students){
        if(students[key] >= 1){
            answer++;
        }
    }
    return answer;
}