[완전탐색] K번째 큰 수

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

1부터 100 사이의 자연수가 적힌 N장의 카드가 있으며 이 카드는 같은 숫자의 카드가 여러장 존재할 수 있다.

이 중 3장을 뽑아 3장의 카드에 적힌 수의 합을 구한다.

N장의 카드 중 3장을 뽑는 모든 경우의 수에 대해 그 합 중 K번째로 큰 수를 출력한다.

이때 중복되는 값은 제외한다.

 

 

👉 입력

카드의 갯수(N)와 K가 입력되고 N개의 카드값이 입력된다.

 

 

👈 출력

K번째 수를 출력한다. K번째 수가 존재하지 않으면 -1을 출력한다.

 

 

📝 풀이

 

function solution(n, k, card) {
    let answer = [];

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                if (answer.indexOf(card[i] + card[j] + card[k]) === -1) {
                    answer.push(card[i] + card[j] + card[k])
                }
            }
        }
    }
    answer.sort((a, b) => b - a);

    return answer[k - 1] === undefined ? -1 : answer[k - 1];
}

let arr = [13, 15, 34, 23, 45, 65, 33, 11, 26, 42];
console.log(solution(10, 3, arr));

 

삼중 for문을 돌며 N개의 카드 중 3장을 뽑는 모든 경우의 수를 구한다.

이때 3장의 카드를 더한 값이 answer에 없다면 answer에 더한 값을 넣는다.

 

for문의 모든 순회가 끝났을 때 answer에는 중복 없이 3장의 카드의 합만 남게 되므로 K번째 큰 수를 출력하기 위해 이를 내림차순으로 정렬한다.

 

이후 K번째 수는 k-1의 인덱스를 가지고 있으므로 answer[k-1]을 출력하는데 이때 해당하는 수가 없다면 undefined의 값을 가지게 된다.

따라서 answer[k-1]이 있다면 그 수를, 없다면 -1을 리턴, 출력한다.

 

 

function solution(n, k, card) {
    let answer = [];
    let s = 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++) {
                s.add(card[i] + card[j] + card[k]);
            }
        }
    }
    answer = Array.from(s).sort((a, b) => b - a);

    return answer[k - 1] === undefined ? -1 : answer[k - 1];
}

let arr = [13, 15, 34, 23, 45, 65, 33, 11, 26, 42];
console.log(solution(10, 3, arr));

 

중복을 제거하는 부분을 좀 더 효율적으로 바꾸기 위해서는 Set 객체를 사용하면 된다.

Set은 중복은 자동으로 걸러준다.

따라서 중복을 거르는 추가 작업 없이 Set에 넣어준 후 이를 배열로 바꾸고 정렬한 뒤 K번째 수를 리턴, 출력하면 된다.