[완전탐색]k번째 큰 수

문제

현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있다 (같은 숫자의 카드가 여러장 있을 수 있다). 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값의 경우를 기록하려고 한다.기록한 값 중 K번째로 큰 수를 출력하고자 한다.

 

문제풀이

1. 세 개의 수를 뽑은 뒤 합산 한 모든 경우의 수를 구해야 하기 때문에 3중 for문을 이용한다.   

   이때 자기 자신은 뽑아야 되는 수 중 제외해야 하기 때문에 중첩 for문 내의 초기 인덱스값은 이전 for문 내의 초기 인덱스 값에  1을

   가산해 준다.   

 

2. 3번째로 큰 수를 구하기 위해서 합산 한 모든 결과값에 대한 배열에 대해서 반복문을 수행해 준다.   

    이때 기준이 될 가장 맨 앞의 값이 배 열 내에서 최댓값이 되어야 하기 때문에 내침차순으로 정렬해 준다.   

    최댓값보다 작을 경우 식별 변수 cnt를 가산해준다. 가산 된 cnt와 k(=3)의 값이 같은 경우 해당 인덱스의 수를 정답 처리한다.

 

코드

function solution(arr) {
  let answer= 0;
  let sumArr = [];
  let max = Number.MIN_SAFE_INTEGER;
  let cnt = 1;

  for(let i = 0; i < arr.length; i++) {
    for(let j = i + 1; j < arr.length; j++) {
      for(let z = j + 1; z < arr.length; z++) {
        let sum = 0;
        sum = arr[i] + arr[j] + arr[z];
        sumArr.push(sum);
      }
    }
  }

  sumArr.sort((a, b) => b - a);

  for(let i = 0; i < sumArr.length; i++) {
    if(max < sumArr[i] && cnt === 1) {
      max = sumArr[i];
    }
    else if(max > sumArr[i]) {
      cnt++;
      if(cnt === 3) {
        answer = sumArr[i];
      }
    }
  }

  return answer;
}

let arr = [13, 15, 34, 23, 45, 65, 33, 11, 26, 42];

console.log(solution(arr));

 

문제풀이2

1. k번째 큰 수를 구하기 위해서 for문을 한번 더 수행하지 않기 위해 중복되지 않은 자료구조인 Set 객체를 활용하여     내림차순만으로 k번째(인덱스[k - 1])로 큰 수를 구할 수 있다.

 

코드

function solution(n, k, card){
                let answer;
                let tmp = new Set();
                for(let i=0; i<n; i++){
                    for(let j=i+1; j<n; j++){
                        for(let k=j+1; k<n; k++){
                            tmp.add(card[i]+card[j]+card[k]);
                        }
                    }
                }
                let a=Array.from(tmp).sort((a, b)=>b-a);
                answer=a[k-1];
                return answer;
            }
            
            let arr=[13, 15, 34, 23, 45, 65, 33, 11, 26, 42];
            console.log(solution(10, 3, arr));