[완전탐색(블루투포스)] - k번째 검색

문제

 

1~100사이 자연수 N장 카드가 있다.

같은 숫자의 카드가 여러장 있을 수 있다.

3장을 뽑아 합한 값을 기록한다.

기록값중 k번째로 큰 수는 무엇인가?

(25 25 23 22 중에서 k값이 3이면 K번째 큰 값은 22이다. <- 중복허용X 한다는 말)

 

입력예제:

13 15 34 23 45 65 33 11 26 42

출력예제:

143

 

풀이

 

중복값을 허용하지 않기때문에 JS 의 Set 자료구조를 사용해서 세 카드값의 합을 담는다.

그러면 set자료구조에는 중복이 없는 값이 담긴다.

 

예를들어 10장의 카드가 있다고 하면 3장을 뽑을때 완전탐색을 이용해서 set자료구조에 값을 넣는다.

그 값을 array로 바꾸고 내림차순으로 바꿔준다.

그 배열의 k번째 값을 출력하도록 한다.

 

코드

 

function solution(n, k, card){
  let answer;
  let tmp = new Set(); //중복값을 넣지 않기 위해 Set 자료구조 사용
  for (let i = 0; i < n; i++) { // 완전탐색으로 카드를 찾는다, i < n 해도되고 i < n-2해도된다.
    for (let j = i+1; j < n; j++) { // j < n해도되고, j < n - 1해도 된다.
      for (let l = j+1; l < n; l++) {
        tmp.add(card[i]+card[j]+card[l]); //Set 자료구조는 add로 값을 담는다.
      }
    }
  }
  let tmp2 = Array.from(tmp).sort((a, b) => b - a); // set -> array로 변경하고, 내림차순한다.
  console.log(tmp2);
  answer = tmp2[k-1]; //배열의 k번째 값을 담는다.
  return answer;
}

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

 

출처

 

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

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의