[04.완전탐색] 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

---

결과

X

내가 푼 방식

const solution = (k,array) => {
  const n = array.length;
  let sumArray = [];
    for(let i=0; i < n; i++) {
      let sum = 0
      for(let k=0; k < n; k++) {
        if(i !== k) {
          sum = array[i] + array[k]
        }
        for(let j=0; j < n; j++) {
          if((j !== k) && (j !== i)){
            sum = sum + array[j]
            sumArray.push(sum)
          }
        }
      }
	}
  console.log(sumArray)
}

 접근과정

1. 문제는 심플하다. 서로 다른 세 수를 세 번의 반복문을 통해 뽑아 더 해 큰 수부터 정렬하여 k번째 큰 수를 리턴하면 된다.

문제점

1. 두 번째 반복문에서 i와 다른 k 라는 조건문을 걸었다고 하더라도 세 번째 반복문에서 i와 k가 다르다는 보장이 되지 않는다.
2. 세 번째 반복문에서 sum이 초기화 되지 않은 채 계속 누적된 값이 push 되었다.

 

---

모범답안

[답안 보고 짠 방식]

const solution = (k,array) => {
  const n = array.length;
  let sumArray = [];
    for(let i=0; i < n; i++) {
      let sum = 0
      for(let k=i+1; k < n; k++) {
        for(let j=k+1; j < n; j++) {
            sumArray.push(array[i]+array[j]+array[k])
        }
      }
	}
  sumArray.sort((a,b) => b - a);
  console.log(sumArray)
  return sumArray[k-1];
}

[모범답안]

function solution(test){
    let answer=0;
    m=test.length;
    n=test[0].length;
    for(let i=1; i<=n; i++){
        for(let j=1; j<=n; j++){
            let cnt=0;
            for(let k=0; k<m; k++){
                let pi=pj=0;
                for(let s=0; s<n; s++){
                    if(test[k][s]===i) pi=s;
                    if(test[k][s]===j) pj=s;
                }
                if(pi<pj) cnt++;
            }
            if(cnt===m) answer++;
        }
    }
    return answer;
}

리뷰