[Lv.1] 과일 장수 (예제로 알아보는 JS 배열의 시간복잡도)

1. 문제

2. 풀이 1 ( 안되는 풀이)

function solution(k, m, score) {
    var answer = 0;
    let arr = score.sort((a,b)=>b-a) 큰 순서대로 배열을 정렬

    while(arr.length>=m){ m으로 나눠지지 않을때까지
        let f = arr.splice(0,m); 앞쪽부터 m만큼 잘라서
        answer+= m * Math.min(...f) 자른것의 최소값(점수) * 갯수(m) 을 answer에 계속 더해준다.
    }
    
    
    return answer; //하지만 이거 안된다.
}

이렇게 풀었는데 시간초과로 통과를 못하네?

로직은 맞는데..?

그래서 한참 검색하다가 발견한 이유

배열 메소드의 시간복잡도 때문이다.

 

시간 복잡도를 표기할 땐 대체로 빅오 표기법으로 사용한다.

1. O(1) : 상수 시간 복잡도

   - 어떤 수가 들어와서 몇번 계산을 해도 괄호 안 상수만큼 시간 복잡도는 동일하다.

2. O(n) : 

   - n만큼의 시간 복잡도이다. n만큼 수행한다 ( ex : n번만큼 순회하는 for문)

3. O(logN) :

   - logN만큼의 시간 복잡도이다. ( ex : 8 -> 4 -> 2 -> 1 번 실행)

4. O(N^2) : 

   - n^2만큼의 시간 복잡도로, n^2만큼 수행한다 ( ex : 2중 for문)

 

그렇다면 JS의 배열 메소드 총정리 빠르게

array.push(a)	배열의 맨 끝에 a 삽입	O(1)
array.pop()	배열의 맨 끝의 값을 삭제	O(1)
array.shift(a)	배열의 맨 앞에 a 삽입	O(n)
array.unshift()	배열의 맨 앞에 값을 삭제	O(n)
array.concat(a1,a2, ...)	배열 합치기	O(n)
array.slice(시작,종료)    (종료없으면 끝까지)	시작부터 종료까지 복사본의 배열 추출, 원본이 변경되지 않음	O(n)
splice(시작,종료)    (종료없으면 끝까지)	시작부터 종료까지 추출, 원본이 변경됨.	O(n)
sort(option)	정렬	O(nlog(n))
array.forEach((e, i, array)=>{callback})	배열 순회 e : 요소 i : index array : array 그 잡채	O(n)
array.map((e,i, array)=>{callback})	모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 가진 새로운 배열을 리턴한다. e : 요소 i : index array : array 그 잡채	O(n)
array.filter((e,i,array)=>{callback})	조건을 통과한 요소들을 새로운 배열로 반환한다. e : 요소 i : index array : array 그 잡채	O(n)
array.reduce((누산기,e,i,array)=>{callback})	배열의 각 요소에 대해 누산기를 적용하고 배열을 축소하여 하나의 값으로 반환한다. 누산기 : 누산기 e : 요소 i : 현재 index array : array 그 잡채	O(n)

결론

sort, while, splice, min, 또한 중첩으로 인해 시간 복잡도가 매우 높다. 따라서

반복문을 최대한 줄이는 알고리즘으로 시간 복잡도를 줄여 효율성을 높인다.

function solution(k, m, score) { //k는 최대점수, m은 한상자의 사과수, score는 사과점수들의 배열
    var answer = 0;
    
    let arr =[]; // 빈배열 생성
    arr.length =k; // 빈 배열의 길이를 k로 정함
    arr.fill(0); // k개의 배열 각 요소를 0으로 채워줌
    for(let i=0; i<score.length; i++){ 
        arr[k-score[i]]++;
        // 배열의 (최고점수-각사과의점수) 번째에 score의 사과 갯수를 각각 채워줌
     } 
    // ex) arr = [4점 3개, 3점 2개, 2점 1개, 1점 4개]; = [3,2,1,4]
    // ex2) arr = [6점 1개, 5점 3개, 4점2개, 3점 1개, 2점 2개, 1점 0개]
    //			= [1,3,2,1,2,0] 이런식임
  
  	//전략 : 각 요소를 한상자의 사과수로 나눈 몫은 그 점수로만 이루어진 사과박스이고,
    //		 나눈 나머지는 다음 배열로 넘겨서 더하면 어차피 그 배열의 최소점수가 그 박스의 점수이므로
    //       걍 넘겨서 같이 세도 상관없음.
    //       그래서 몫*갯수 를 합해주면 된다.
    for(let j =0; j<k; j++){
        let 몫 = Math.floor(arr[j]/m) //이는 k-j 만큼의 가격
        let 나머지 = arr[j] % m; //이는 다음으로 넘겨줌
        answer += 몫*(k-j)*m;
        arr[j+1] += 나머지;
    }

    return answer;
}

for 반복문 2개지만, 시간복잡도는 O(score.length+k) 로 매우 줄어들었다!

 

통과!