알고리즘-2021/03/30

sanghun Lee·2021년 3월 30일

알고리즘

목록 보기

4/52

문제 설명

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

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

제한사항

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

입출력 예

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

풀이

//n: 전체 학생수, lost: 도난당한 학생들의 배열, reserve:여벌의 체육복을 가져온 학생들의 번호가 담긴 배열
//return:체육수업을 들을 수 있는 학생의 최댓값
//인접한 배열에게만 체육복 빌려주기가능


//n만큼 반복문 돌면 될 것 같고
//n만큼 map을 만들자 -> 기본 1로가고 lost인경우 0
//그리고 reserve를 통해서 +1or -1키에 해당하는 곳이 0이면 +1하자

function solution(n, lost, reserve) {
    var answer = 0;
    let map = {};
  
    //전체 학생 수 만큼 mapping을 위한 객체 생성
    for(let i =0; i < n; i++){
      map[`${i+1}`] = 1;
    }
    //잃어버림에 해당하는 곳에 -1을 연산
    lost.forEach((el,index)=>{
      map[`${el}`] -= 1;
    })
    //reserve에 해당 키 존재시 +1 하고 
    reserve.forEach((el)=>{
      map[`${el}`] +=1
    })
    //lost로 회문을 돌려 앞 뒤에 존재하는 키의 값이 1 초과 시 가져오는 방향
    lost.forEach((el,index)=>{
      if(map[`${el+1}`] > 1 && map[`${el}`] < 1){
        map[`${el+1}`] -=1
        map[`${el}`] += 1
      }
      if(map[`${el-1}`] > 1 && map[`${el}`] < 1){
        map[`${el-1}`] -=1
        map[`${el}`] += 1
      }
    })
  //값들을 모아 놓은 배열을 만들어 1이상이 된다면 answer카운트 증가
    let mapValue = Object.values(map);
    mapValue.forEach((el,index)=>{
      if(el>=1) answer +=1;
    })
    return answer;
}

의외로 굉장히 빨리 풀어서 테스트케이스를 돌렸으나 몇가지 통과를 하지못해 당황한 문제이다..
아무래도 문제가 되었던 부분은 reserve와 lost를 회문돌리는 마지막 쪽인데
처음에는 reserve에서 count+1을 하고 근처에(+1 or -1)키의 값이 0 이면 이라는 조건을 넣어 다시 연산하려 하였다.

그런데 몇가지 테스트케이스가 엇나간걸로 보아 아마도 문제 조건 중 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 에 걸렸던 것 같다.

그래서 따로 회문을 돌리고 그냥 사고의 방식대로 알고리즘을 정렬해나아가니 해결이 되었다.

PS.forEach말고 좋은 것을 좀 찾아봐야겠다... filter의 활용도를 높여보자