본문 바로가기

프로그래머스/Greedy

[그리디] 프로그래머스 '체육복' - js

반응형

1. 문제

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

2. 코드

이 문제의 핵심은 정렬이다.

lost = lost.sort((a,b) => a-b);

테케 13,14번이 계속 통과가 안돼서 레벨 1인데도 왜 이렇게 못풀지 싶어 자괴감이 들었는데, 알고보니 lost 배열이 [1,2,3] 이렇게 주어질 수도 있지만 [3,1,2] 이렇게 주어질 수도 있어 정렬을 해줘야 모두 정답처리가 되는 것이였다.

이걸 알고 나니 너무 허무했다는거~! 시간을 겁나 쏟았는데~~!!!

function solution(n, lost, reserve) {
    let count = n - lost.length;
    lost = lost.sort((a,b) => a-b);
    
    for(let i=0;i<lost.length;i++){
    	// 더 이상 여벌 체육복을 가져온 학생 후보가 없으면
        if(!reserve.length) break;
        // 여벌 체육복을 가져온 학생도 도난당했으면
        if(reserve.includes(lost[i])) { 
            reserve.splice(reserve.indexOf(lost[i]),1); count++; 
        }
        // 체육복을 가져오지 않은 학생의 앞 또는 뒤 학생이 여벌 체육복을 가져온 학생이 도난 당하지 않았으면
        // 최대한 많은 학생에게 빌려주기 위해 앞 학생이 여벌 체육복 있으면 앞 학생에게 빌리도록
        else if(reserve.includes(lost[i] - 1) && !lost.includes(lost[i] - 1)) {
            reserve.splice(reserve.indexOf(lost[i] - 1),1); count++;
        }else if(reserve.includes(lost[i] + 1) && !lost.includes(lost[i] + 1)) {
            reserve.splice(reserve.indexOf(lost[i] + 1),1); count++;
        }
    }
    
    return count;
}

 

다른 사람의 풀이)

이 풀이도 너무 깔끔하고 좋은 것 같다!

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;
}
반응형