문제설명

설계 과정

• 어떤 종류의 수가 있는지 알 수 있는 배열 => numArr = [];
• 동일한 수가 몇개 들어가 있는지 알 수 있는 배열 => countArr=[];
  
  
  위와 같이 초기 배열들을 만들고 진행

1. 입력값을 하나씩 아래과정을 실행한다.
   만약에 numArr에 없는 값이라면, numArr에 추가하고 이게 입력값 배열에 몇개 있는 count를 세준다.
   세준 후, 이를 countArr에 추가
2. 구한 countArr을 오름차순으로 정렬
3. countArr을 하나씩 pop해주면서 k가 0보다 작거나 같아질때까지 빼준다. 이때 뺄 때마다 answer++을 해준다.

초기 코드

function solution(k, tangerine) {
    var answer = 0;
    var numArr=[];
    var countArr = [];
    for(var i =0;i<tangerine.length;i++){
        //처음 보는 수라면,
        if(numArr.indexOf(tangerine[i])===-1){
            numArr.push(tangerine[i]);
            var count = 0
            tangerine.forEach(element=>{
                if(element===tangerine[i]){
                    count++;
                }
            })
            countArr.push(count);
        }
    }
    
    //countArr을 오름차순으로 정렬
    countArr.sort((a,b)=>{
        return(a>b?1:-1);
    })
    
    while(k>0){
        k = k - countArr.pop();
        answer++;
    }
    return answer;
}

결과

우선 시간초과가 난 것을 볼 있고, 통과한 테스트도 시간복잡도가 높은 것을 확인할 수 있다. 이는 입력값을 한번 돌고, 또 그 안에서 몇개인지 찾는 과정이 있다. 이 부분이 굉장히 시간이 많이 들것이다. 이러한 부분을 해결할 설계가 필요하다.

개선 설계

설계 과정은 이전 과정과 비슷하지만, 이번엔 `hash` 를 사용해서 문제에 접근했다. 

• hashMap을 하나 만들고 시작하자
  1) 입력값을 하나씩 확인하면서 아래 과정을 실행한다.
  입력값이 hashMap에 key 값으로 가지고 있나?
  -> 없다면 추가해준다.
  -> 있다면 value++를 해준다.
  2) 한바뀌 돌면서 해시를 만들었다면 이를 정렬한다.
  3) 큰 것부터 k를 빼주면서 0이 될때까지 빼준다.
  -> 이때 뺄때마다 answer++ 를 해준다.

개선 코드

function solution(k, tangerine) {
    var answer = 0;
    var hashMap = new Map();
    
    //해시에 key, value값 넣기
    for(var i = 0;i<tangerine.length;i++){
        if(hashMap.has(tangerine[i])){
            hashMap.set(tangerine[i],hashMap.get(tangerine[i])+1);
        }
        else{
            hashMap.set(tangerine[i],1);
        }
    }
    //해시 맵 정렬
    hashMap = [...hashMap].sort((a,b)=>a[1] - b[1]);
    while(k>0){
        k-=hashMap.pop()[1];
        answer++;
    }
    return answer;
}

결과

이번 문제는 시간복잡도를 어떻게 줄이느냐가 중요했던 것 같다. 해시를 사용하기 이전에는 for문 안에 for문이 있는 코드였다. 딱봐도 시간복잡도가 높다. 하지 해시를 사용함으로써 for문 한번으로 코드를 줄였다. 이 덕분에 시간 복잡도가 줄었다.


코드를 구현함에 있을때, 단순히 문제를 풀기위한 것 뿐만 아니라 효율적인 코드를 짜는 것이 중요하다는 것을 느낄 수 있다.