귤 고르기

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.
예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.
경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

입출력 예

k	tangerine	result
6	[1, 3, 2, 5, 4, 5, 2, 3]	3
4	[1, 3, 2, 5, 4, 5, 2, 3]	2
2	[1, 1, 1, 1, 2, 2, 2, 3]	1

처음에 푼 코드

function solution(k, tangerine) {
	let arr = [...new Set(tangerine)].map(x=> [x]);
    for (let i=0;i<arr.length;i++){
        arr[i].push(tangerine.filter(element => 
        arr[i][0] === element).length)
    }
    
    arr.sort((a,b)=> b[1]-a[1]);
	
    let newarr = []
    for(let i of arr){
        for(let j of tangerine) {
            if(j === i[0]) newarr.push(j);
        }
    }
    
    let newarr2 = [...new Set(newarr)];
    
    return newarr2.indexOf(newarr[k-1])+1;
    } 

let arr = [...new Set(tangerine)]
먼저 tangerine배열을 new Set을 이용하여 유니크한 배열로 만들었다.

2차원 배열을 생성하여 각 요소의 인덱스0에는 각 tangerine값을 넣고 인덱스1에는 출연빈도를 넣었다.
빈도가 높은 순으로 재정렬하였고 k의 위치에 해당하는 인덱스를 처음에 만든 유니크한 배열에서 찾아 값을 return 했다.

다시 해결한 코드

function solution(k, tangerine) {
    var answer = 0;
    var arr = [[]];
    
    tangerine.sort((a,b) => a-b);
    arr[0].push(tangerine[0]);

	for (let i=1; i<tangerine.length; i++){
        let lastArr = arr[arr.length-1];
        if (lastArr[0]!== tangerine[i]) arr.push([tangerine[i]]);
        else {lastArr.push(tangerine[i])}    
    }
    
    arr.sort((a,b)=> b.length - a.length);
    let sum = 0;
    for(let i=0; i<arr.length ;i++){
        sum+= arr[i].length;
        if(sum>=k){
            answer+= i+1;
            break;
        }
    }
    return answer;
}

1차원의 tangerine배열에 새로운 요소를 추가하거나 삭제하지 않고,
새로운 2차원 배열에 출연 빈도 순으로 담았다.
arr.sort((a,b)=> b.length - a.length)
각 배열요소의 길이순으로 정렬하여 문제를 풀었다.

처리속도 차이의 원인

두 코드의 효율성 테스트 결과가 극명하게 차이가 난다. chatGPT에게 물어본 두 코드의 차이점은 아래와 같다.

알고리즘의 차이:

두 함수는 같은 문제를 해결하고 있지만, 알고리즘이 상이합니다. 첫 번째 함수는 배열을 생성하고 정렬하여 값을 찾아내는 방식으로 문제를 해결하고 있습니다. 반면에 두 번째 함수는 주어진 배열을 정렬하고 그룹화하여 값을 찾아내는 방식으로 문제를 해결하고 있습니다.

사용한 자료구조의 차이:

두 함수는 문제를 해결하기 위해 사용한 자료구조가 다릅니다. 첫 번째 함수는 Set과 배열을 사용하여 문제를 해결하고 있지만, 두 번째 함수는 배열을 사용하여 문제를 해결하고 있습니다. Set은 중복된 값을 제거할 때 유용하게 사용할 수 있으며, 배열은 데이터를 순회할 때 유용하게 사용할 수 있습니다. 따라서 두 함수는 다른 자료구조를 사용하고 있기 때문에 처리 속도 차이가 발생합니다.

코드의 최적화:

두 함수는 코드 최적화에 대한 차이가 있습니다. 첫 번째 함수는 filter() 메소드를 사용하여 값을 찾아내고 있지만, 두 번째 함수는 for문을 사용하여 값을 찾아내고 있습니다. filter() 메소드는 배열의 요소를 순회하며 주어진 함수의 조건에 맞는 요소만을 추출하여 새로운 배열을 만들어 반환합니다. 하지만 이 과정에서 새로운 배열을 생성하고 메모리를 할당하므로 처리 속도가 느릴 수 있습니다. 반면에 for문은 변수를 초기화하고 조건식을 평가하며 값을 할당하는 등의 과정이 필요하지만, 메모리 할당이 필요하지 않기 때문에 처리 속도가 빠릅니다.

유의미하고 생각되는 부분

filter()메소드는 배열의 모든 요소를 순회하며 새로운 배열을 만드는 과정에서 메모리를 할당하므로 처리속도가 느릴 수 있다.

반면 for문은 메모리 할당이 필요하지 않기 때문에 처리 속도가 빠르다.

comment

사실 filter, map, reduce등의 메소드는 워낙 코드가 간결하기 때문에 더 우선하여 사용하게 되는 것 같다. 하지만 코드의 간결성과 최적화는 완전히 다른 문제이기 때문에 이 부분을 유의해야할 것 같다.