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
문제를 이해해보자.
우선 1~100사이의 자연수에서 3장의 카드를 뽑는다. 그 3장을 뽑을 수 있는 모든 경우의 수를 기록하고,
그 기록한 값중에 k번째(몇번인지를모름) 의 큰 수를 출력하는 것이다.
📌작성코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n, k, card) {
let answer = 0;
let sum = 0;
let set = new Set() // 중복된 값을 없애주기 위한 Set 생성자 사용
let arry = []
for (let i = 0; i < card.length; i++) { // 카드 3장을 뽑는 모든 경우를 기록하기 위해 반복문 3개 돌림
for (let j = i + 1; j < card.length; j++) {
for (let s = j + 1; s < card.length; s++) {
sum = card[i] + card[j] + card[s] // 카드 3장을 뽑고 더한 값을 저장
set.add(sum) // set 생성자에 카드 3장의 합을 넣고 중복되는 값을 제거
arry = Array.from(set).sort((a, b) => (b - a)) // 모든 결과를 배열로 만들어주고 내림차순 정렬
answer = arry[k - 1] // k번째 카드를 뽑는다.
}
}
}
return answer;
}
let arr = [13, 15, 34, 23, 45, 65, 33, 11, 26, 42];
console.log(solution(10, 3, arr));
</script>
</body>
</html>우선 3장의 카드를 뽑아야한다고 했으니, for문을 3번 돌려준다.
처음 반복문에서는 첫번째 카드부터 뽑으니 상관없지만
두번째 반복문부터는 두번째 카드부터 뽑아야하기때문에 i + 1 (직전카드에서 +1해줌) 을 해준다.
세번째 반복문도 세번째 카드부터 뽑아야하니까 직전카드 + 1 j+1 을 해준다.
3장의 뽑은 카드의 합합 값을 sum 변수를 지정해서 값을 넣어준다.
그다음 set 생성자를 사용하여 중복된 값을 없애준다.
(set 생성자를 사용하지않으면 중복된 값이 생김!)
모든 결과물을 배열로 만들어주기위해 Array.from 생성자 함수를 사용하고
앞에서 중복값을 없애기 위해 사용했던 set함수를 넣어준다.
값이 큰 순서에서 작은 순서대로 나열 되어야하기때문에 sort를 사용하여 내림차순으로 정렬을 시켜준다.
우리가 뽑아야하는 카드는 k번째 카드이기때문에 arry[k -1] 을 해서 answer에 넣어준다.
(-1을 해준 이유는? 예를들어 3이 k번째로 들어온다고치자.
0, 1, 2, 3, 4가 들어오면 우리가 원하는 값은 '2'인데 3번째는 '3'이 되기때문에 -1을 해준다.)
'알고리즘' 카테고리의 다른 글
| [알고리즘 문제] 5-2번 (0) | 2022.06.17 |
|---|---|
| [알고리즘 문제] 5-1번 (0) | 2022.06.17 |
| [알고리즘 문제] 4-4번 (0) | 2022.06.16 |
| [알고리즘 문제] 4-3번 (1) | 2022.06.13 |
| [알고리즘 문제] 4-2번 (0) | 2022.06.13 |