4-5 k번째 큰수

문제설명

중복된 숫자가 있을수도 있는 N장의 카드에서 무작위로 3장을 뽑아 더한 모든 경우의 값을 구하고

그중에서 k번째로 큰 수를 구해라.

예를 들어 k 가 3이고, 3장을 더한 모든 경우의 값이 [10, 10, 11, 11, 12, 12, 13] 인 경우

k번째로 큰 수는 12 이다.

const numList = [13, 15, 34, 23, 45, 65, 33, 11, 26, 42];
const k = 3;

numList는 카드의 목록이다.

 

접근방법

4챕터 막문제라 엄청 어려울줄 알았는데 생각보다 쉽게 풀었다.

3중 for문 돌리면서, 중복되는 경우 제외 해주면서 싹다 더해준 뒤에

배열하나에 중복되는 값 거르면서 때려넣고,

내림차순 정리한다음에

k-1번 index의 값을 출력하면 된다.

 

function solution(k, numList) {
  let sum = 0;
  const sumList = [];
  const length = numList.length;

  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      for (let s = j + 1; s < length; s++) {
        sum = numList[i] + numList[j] + numList[s];
        if (!sumList.includes(sum)) sumList.push(sum);
      }
    }
  }
  sumList.sort((a, b) => b - a);
  return sumList[k - 1];
}

const numList = [13, 15, 34, 23, 45, 65, 33, 11, 26, 42];
const k = 3;
console.log(solution(k, numList));

sum에다 0할당하고

모든 sum값을 때려넣을 배열 sumList 선언했다.

 

3중 for문인데,

i는 0부터

j는 i+1 부터

s는 j+1 부터 돌려서

중복되는 경우를 걸러냈다.

 

sum 에다가 arr[i],arr[j],arr[s] 더한 값 재할당해주고,

if문의 조건에 includes를 사용하여,

중복되는 값을 제외 하고 sum을 sumList에 다 때려넣는다.

 

for문이 끝나면 sumList를 내림차순으로 정리하고

sumList[k-1]을 리턴한다.

 

위의 입력 예제에선 143이 출력되고,

내림차순으로 정렬된 sumList 는 

[

152, 144, 143, 141, 140, 136, 133, 132, 130, 125, 124, 123,

122, 121, 120, 118, 114, 113, 112, 111, 110, 109, 106, 105,

104, 103, 102, 101, 100, 99, 98, 94, 93, 92, 91, 90,

89, 88, 87, 86, 84, 83, 82, 81, 80, 79, 78, 76,

75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 64, 62,

61, 60, 59, 58, 57, 54, 52, 51, 50, 49, 47, 39

]

이다.

 

인프런센세 코드

function solution2(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));

센세 코드와 내 코드가 비슷한 경우는 센세코드는 잘 안올리는데,

 

표준 내장 객체인 Set이용한게 너무 아름답다.

Set객체는 중복되는 값은 포함하지 않고,

일반 객체와 달리 length를 가지고 있어서 index를 이용한 탐색이 가능하다.

 

알고있는거랑 사용할 수 있는건 참 많이 다르다.