[JavaScript/section 4] 05 - K번째 큰 수

📌 문제

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

만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19.....이고 K값이 3이라면 K번째 큰 값은 22이다.

 

📝 풀이

🧑🏻‍💻 나의 풀이 방법

• 3중 for문을 사용하여 N장의 카드 중 3장의 카드를 뽑고 카드에 적힌 수를 합한 값을 배열에 저장한다.
• 배열에 저장된 값을 내림차순으로 정렬하고 Set 객체를 사용하여 중복을 제거한다.
• 다시 스프레드 연산자를 사용하여 중복 값이 제외된 새로운 배열을 만든 후 K번째 큰 값을 찾는다.

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

  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++) {
        const sum = card[i] + card[j] + card[k];
        arr.push(sum);
      }
    }
  }

  answer = [...new Set(arr.sort((a, b) => b - a))][k - 1];
  return answer;
}

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

 

👨🏼‍🏫 강사님 풀이 방법

강사님은 처음부터 Set 객체를 생성하여 add() 메서드를 사용해 값을 저장하면서 유일한 값을 저장한다. (Set -> 배열)

나의 풀이 방법(배열 -> Set -> 배열)에 비해 변환하는 과정이 줄었다는 것을 확인할 수 있다.

• Set 객체를 생성한다.
• 3중 for문을 사용하여 N장의 카드 중 3장의 카드를 뽑고 카드에 적힌 수를 합한 값을 add() 메서드를 사용하여 Set 객체에 추가한다. (Set 내의 값은 유일해야 하기 때문에 값이 같은지 검사를 수행)
• Array.from() 메서드를 사용하여 Set 객체를 배열로 변환한 후 내림차순으로 정렬한다.
• 정렬된 배열에서 K번째 큰 값을 찾는다.

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));

 

📚 참고한 사이트

Set - JavaScript | MDN