- 어떤 종류의 수가 있는지 알 수 있는 배열 => numArr = [];
- 동일한 수가 몇개 들어가 있는지 알 수 있는 배열 => countArr=[];
위와 같이 초기 배열들을 만들고 진행
- 입력값을 하나씩 아래과정을 실행한다.
만약에 numArr에 없는 값이라면, numArr에 추가하고 이게 입력값 배열에 몇개 있는 count를 세준다.
세준 후, 이를 countArr에 추가- 구한 countArr을 오름차순으로 정렬
- 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문 한번으로 코드를 줄였다. 이 덕분에 시간 복잡도가 줄었다.
코드를 구현함에 있을때, 단순히 문제를 풀기위한 것 뿐만 아니라 효율적인 코드를 짜는 것이 중요하다는 것을 느낄 수 있다.