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

Jetom·2023년 3월 23일
0

Javascript

목록 보기
22/25
post-thumbnail

탐욕법(greedy) 알고리즘이 제일 쉬운거라는데...? 이거 맞아??😂😂😂😂😂


👉 문제 풀러가기 : https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=javascript


😎 문제

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

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

제한사항

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

입출력 예

nlostreservereturn
5[2, 4][1, 3, 5]5
5[2, 4][3]4
3[3][1]2

🥴 문제풀이

function solution(n, lost, reserve) {
  //Array를 n만큼 생성한 뒤 1로 초기화 시켜줌
  //[1,1,1,1,1]
  const students = new Array(n).fill(1)
  
  //최종적으로 체육복을 가지고 있는 학생 수 카운팅하는 변수
  let result = 0
  
  for(let i = 0; i < lost.length; i++){
    //lost[i]-1과 lost[i-1]을 헷갈리지말자
    //lost[i]-1은 배열의 요소 값을 -1 시키는것이고, lost[i-1]은 배열 index를 -1 시킴
    //students[lost[i]-1]--와 students[lost[i]-1]-1도 헷갈리지말자
    //students[lost[i]-1]--은 감소 시킨 값을 다시 할당해주는 방면 students[lost[i]-1]-1은 students에 -1을 하지만 할당을 하지않고 그냥 끝낸다 
    //따라서 students[lost[i]-1]--을 하거나 students[lost[i]-1]-=1을 하는게 좋음
  	students[lost[i]-1]--
  }
  
  for(let i = 0; i < reserve.length; i++){
    //배열의 인덱스는 0부터 시작하고 우리가 찾는 애는 1부터 시작하니까 i-1을 해야됨
    //reserve[i]+1을하면 2,4,6이 되겠쥬?
    //그럼 엉뚱하게 결과가 나옴!
    //[ 1, 0, 2, 0, 2, <1 empty item>, NaN ] 요렇게!
  	students[reserve[i]-1]++
  }
  
  //현재 students는 [2,0,2,0,2]인 상태
  
  for(let i = 0; i < students.length; i++){
    //이제 0인 학생에게 여유분 가지고 있는 애한테 노나주기
  	if(students[i] === 0){
      //i가 0이면 없는애고 [i-1]이나 [i+1]이 === 2면 앞뒤 학생이 2개 가지고있는거니까 노나줌
      //그래서 students[i]에는 ++ 해주고 앞이나 뒤는 --해주는것
      if(students[i-1] === 2){
        students[i]++
    	students[i-1]--
      } else if(students[i+1] === 2){
      	students[i]++
        students[i+1]--
      }
    } 
  }
  
  //이제 잘 나눠가졌는지 확인하는 단계
  students.forEach(num => num > 0 && result++)
  
  //forEach는 for문처럼 return을 안해서 result를 최종적으로 return해줘야함
  return result
}

console.log(solution(5,[2, 4],[1, 3, 5])) //5
profile
사람이 좋은 인간 리트리버 신혜리입니다🐶

0개의 댓글