[ 자바스크립트(JavaScript) ] section04 - 5 - K번째 큰 수

📍 33 - K번째 큰 수

100장의 카드 중 3장을 뽑는 모든 경우의 수는 100C3이므로 161,700이다. 여기서 3장을 뽑아 각 카드의 적힌 수를 합하려면 3 중반 복문으로 bruteForce로 모든 경우의 수를 돌려보면 된다. 이 문제의 시간복잡도는 다항 시간인 O(N^3)이지만 N=100일때 최대 1,000,000번 수행하므로 시간 초과에 걸리지 않는다. (보통 반복문을 돌 때 1초당 최대 10^8 (약 1억번) 돌 수 있으므로, N=100일때는 O(N^4)까지는 커버 가능하다.)

 

또, 강의에서는 3중 반복문의 i, j, k의 범위를 모두 n까지로 설정했는데, 맨 마지막에서 k가 n을 벗어나면 반복문에 들지 않고, 마찬가지로 j가 n의 범위를 벗어나도 반복문에 들지 않기 때문에 자동적으로 종료된다고 말씀하셨다. 나는 조금이라도 불 필요한 연산을 줄이기 위해 반복문의 범위를 n-2, n-1, n까지로 설정했다.

 

728x90

 

// 나의 코드
let arr = [13, 15, 34, 23, 45, 65, 33, 11, 26, 42];
let target = 3;
let n = 10;

console.log(solution(n, target, arr))

function solution(n, target, arr){
    let answer = [...new Set([])];

    for (let i=0; i<n-2; i++){
        for (let j=i+1; j<n-1; j++){
            for (let k=j+1; k<n; k++){
                answer.push(arr[i] + arr[j] + arr[k]);
            }
        }
    }
    answer = answer.sort((a, b) => b - a);
    return answer[target-1];
}

 

// 강사님 코드
let arr = [13, 15, 34, 23, 45, 65, 33, 11, 26, 42];
let target = 3;
let n = 10;

console.log(solution(n, target, arr))

function solution(n, k, arr) {
    let ans = new Set();

    for (let i = 0; i < n - 2; i++) {
      for (let j = i + 1; j < n - 1; j++) {
        for (let k = j + 1; k < n; k++) {
          ans.add(arr[i] + arr[j] + arr[k]);
        }
      }
    }
    ans = Array.from(ans).sort((a, b) => b - a);
    return ans[k - 1];
  }