[Javascript] 프로그래머스 LV2 귤 고르기

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

프로그래머스

 

 문제 파악

• 한 상자에 k개의 귤을 담는다.
• 귤을 크기별로 분류했을 때 한 상자에 서로 다른 종류의 수를 최소화하고 싶다.

 

문제 해결 흐름

객체를 사용하여 입력 값으로 주어진 귤들을 크기 별로 분류한다.

	let dir = {};	// 사용할 객체
    // 입력으로 주어진 배열 : tangerine을 map으로 순회한다.
    tangerine.map(e => {
        if(!dir[e]){
            dir[e] = 1
        }else{
            dir[e] += 1;
        }
    })

map 순회를 마치고 dir를 console 찍어보면 이런 식으로 객체에 담겨있다. 

객체를 value 기준 내림차순으로 정렬한다.

let entries = Object.entries(dir);
let sorted_dir = entries.sort((a, b) => b[1] - a[1]);

sorted_dir console 모습

k개의 귤을 선택하여 상자에 담는다. 

서로 다른 크기의 귤을 최소로 상자에 담기 위해서는 sorted_dir 배열에서 가장 마지막 요소부터 제거해주면 된다.

내림차순으로 정렬한 이유는 가장 마지막 요소부터 제거하기 위한 정렬이었다.

오름차순으로 정렬할 경우 가장 처음 요소부터 제거해야하는데, 이런 경우 실행 시간이 낭비되기 때문이다.

 

이제 귤을 제거하는 코드만 남았다.

let count = tangerine.length - k;	// 제거할 귤의 개수
let len = sorted_dir.length			
for(let i=len-1; i>=0; i--){		// 뒤에서부터 순회
    let [A, B] = sorted_dir[i]		// A : 귤의 크기, B : 귤의 개수
    if(count >= B){					// 제거할 귤의 개수가 현재 순회 중인 귤의 개수보다 많다면
        count -= B					// count에서 현재 순회 중인 귤의 개수를 빼준다.
        sorted_dir.pop()			// sorted_dir에서 제거
    }else{							// 제거할 귤의 개수가 현재 순회 중인 귤의 개수보다 적으면 break
        break
    }
}

순회하며 count 개수만큼 귤을 제거. for문 순회를 마치고 sorted_dir console을 찍어본 결과 잘 제거되었음을 확인할 수 있었다.

return sorted_dir.length

결국 현재 배열의 길이는 귤의 종류이므로 배열의 길이를 return한다.

 

 

Javascript

const solution = (k, tangerine) => {
    let dir = {};
    
    tangerine.map(e => {
        if(!dir[e]){
            dir[e] = 1
        }else{
            dir[e] += 1;
        }
    }) 
    let entries = Object.entries(dir);
    let sorted_dir = entries.sort((a, b) => b[1] - a[1]);
    
    let count = tangerine.length - k;
    let len = sorted_dir.length
    for(let i=len-1; i>=0; i--){
        let [A, B] = sorted_dir[i]
        if(count >= B){
            count -= B
            sorted_dir.pop()
        }else{
            break
        }
    }
    return sorted_dir.length
}

console.log(solution(k=6, tangerine=[1, 3, 2, 5, 4, 5, 2, 3]));