[JS] 코딩 테스트 문제 : K번째 큰 수

문제 : K번째 큰 수

문제 설명

현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다. 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다.

3장을 뽑을 수 있는 모든 경우를 기록합니다. 기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요.
만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값은 22입니다.

▣ 입력설명

첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력
된다.

▣ 출력설명

첫 줄에 K번째 수를 출력합니다. K번째 수는 반드시 존재합니다.

▣ 입력예제 1

10 3
13 15 34 23 45 65 33 11 26 42

▣ 출력예제 1

143

내코드

 function solution(n, k, card) {
   let answer;
   let totalArr = []; // 3가지 카드합의 전체 경우의 수를 담는 배열
   let sortArr = []; // 정렬 최종 결과를 담는 배열 (결과를 보기 위함)

   // 총 3가지 카드를 뽑는 반복문
   for (let index = 0; index < n; index++) {
     let firstNum = card[index];
     for (let i = index + 1; i < n; i++) {
       let secondNum = firstNum + card[i];
       for (let j = i + 1; j < n; j++) {
         totalArr.push(secondNum + card[j]);
       }
       secondNum = 0;
     }
     firstNum = 0;
   }

   // console.log(totalArr);
   // console.log(new Set(tempArr));
   sortArr = [...new Set(tempArr)].sort((a, b) => b - a); // 내림차순 정렬
   // console.log(sortArr);
   return sortArr[k - 1];
 }

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

풀이

1. 카드배열을 for 문으로 각각 첫 번째, 두 번째, 세 번째 카드를 정하기 위해 3중으로 반복합니다.
2. 기록 한 값 중 중복되는 부분은 js 내장 객체 set 의 특성을 사용해 중복 부분을 제거하고 다시 배열로 형변환합니다.
3. 중복이 제거된 배열을 Array.prototype.sort 메서드로 로 정렬 합니다.
4. 정렬된 배열의 k 번째 데이터를 반환합니다.

보완할 수 있는 부분

// 현재 코드
let totalArr = []; // 3가지 카드합의 전체 경우의 수를 담는 배열
let sortArr = []; // 정렬 최종 결과를 담는 배열 (결과를 보기 위함)

for (let index = 0; index < n; index++) {
  let firstNum = card[index];
  for (let i = index + 1; i < n; i++) {
    let secondNum = firstNum + card[i];
    for (let j = i + 1; j < n; j++) {
      totalArr.push(secondNum + card[j]);
    }
    secondNum = 0;
  }
  firstNum = 0;
}

sortArr = [...new Set(tempArr)].sort((a, b) => b - a); // 내림차순 정렬

// 보완 코드
let tmpSet = new Set(); //  3가지 카드합의 전체 경우의 수를 담는 SET
let sortArr = []; // 정렬 최종 결과를 담는 배열 (결과를 보기 위함)

for (let index = 0; index < n; index++) {
  for (let i = index + 1; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      tmpSet.add(card[index]+card[i]+card[j])
    }
  }
}

sortArr = [...tmpSet].sort((a, b) => b - a); // 내림차순 정렬

보완 내용

1. Set 에 바로 Set.prototype.add 메서드를 활용해서 바로 데이터를 넣어 기존의 배열에서 Set 으로 형변환 하는 과정 생략
2. firstNum, secondNum 등 불필요한 변수 생략

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard