브루트포스(완전탐색) 문제풀이
자릿수의 합
N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력하는 프로그램을 작성하세요. 자릿수의 합이 같은 경우 원래 숫자가 큰 숫자를 답으로 합니다. 만약 235 와 1234가 동시에 답이 될 수 있다면 1234를 답으로 출력해야 합니다.
자릿수의 합이 최대인 자연수를 출력한다.
- 입력예제
7
128 460 603 40 521 137 123
- 출력예제
137
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const n = Number(input[0]);
const str = input[1].split(" ");
//solution함수 안에 답안을 작성하세요.
function solution(n, str) {
let answer;
let sum_lst = [];
let total;
let max_num = -1;
let max_i;
for (let s of str) {
total = 0;
for (i = 0; i < s.length; i++) {
total += Number(s[i]);
}
sum_lst.push(total);
}
for (let i = 0; i < str.length; i++) {
if (sum_lst[i] > max_num) {
max_num = sum_lst[i];
max_i = i;
} else if ((sum_lst[i] = max_num)) {
if (Number(str[i]) > Number(str[max_i])) {
max_i = i;
}
}
}
answer = str[max_i];
console.log(answer);
}
solution(n, str);
- 풀이 해설
본 풀이는 합을 더한 sum_lst를 추가로 만든 후, 해당 인덱스를 이용해 기존 입력값에서 인덱싱해서 값을 비교했다. (str.lenghth와 n은 같다.)
실제로는 숫자로 입력을 받아 while로 한 번에 풀이할 수 있다.
//오류나서 안푸림
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const n = Number(input[0]);
const nums = input[1].split(" ").map(Number);
//solution함수 안에 답안을 작성하세요.
function solution(n, nums) {
let answer;
let maxNum = 0;
let numRest;
let total = 0;
for (let num in nums) {
do {
console.log(total);
total += num % 10;
num = Math.floor(num / 10);
} while (numRest);
if (total > maxNum) {
maxNum = total;
answer = num;
} else if (total === maxNum) {
answer = Math.max(answer, num);
}
total = 0;
}
console.log(answer);
}
solution(n, nums);
뒤집은 소수
N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하는 프로그램을 작성하세요. 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다. 첫 자리부터의 연속된 0은 무시한다.
첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.
- 입력예제
9
32 55 62 20 250 370 200 30 100
- 출력예제
23 2 73 2 3
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const n = Number(input[0]);
const nums = input[1].split(" ").map(Number);
//solution함수 안에 답안을 작성하세요.
function solution(n, nums) {
let answer = "";
function isPrime(num) {
if (num === 1) return false;
for (i = 2; i < num; i++) {
if (num % i === 0) return false;
}
return true;
}
for (let num of nums) {
let rv_num = 0;
while (num) {
let rem = num % 10; //1의 자릿수
rv_num = rv_num * 10 + rem;
num = parseInt(num / 10);
}
if (isPrime(rv_num)) answer += String(rv_num) + " ";
}
console.log(answer);
}
solution(n, nums);
- 풀이 해설
** 소수 판별 알고리즘 **
소수란, 1과 자기 자신만으로 나누어 떨어지는 자연수를 의미한다. n이 소수인지를 판별하기 위해 1초과 n미만의 자연수로 n이 나누어 떨어지면 (즉 n%i ===0 이면) 소수가 아니다. (약수가 존재하기 때문에)
따라서 아래와 같이 표현할 수 있다.
function isPrime(num) {
for (let i = 2; i < num; i++) {
if (num % i === 0) return false;
}
return true;
}
이때, 짝을 가지는 약수 k는 n의 제곱근보다 작거나 같다. (가령 4의 약수 2는 4의 제곱근과 같다.)
따라서 for문의 범위를 다음과 같이 조정할 수 있다.
for(let i=2; i<parseInt(Math.sqrt(num); i++)
그 밖에 참조할 수 있는 소수판별 알고리즘으로는 '에라토스테네스의 체'가 있다.
** 문자열 뒤집기 **
for (let x of arr) {
let res = Number(x.toString().split("").reverse().join(""));
if (isPrime(res)) answer.push(res);
}
문자열 뒤집기의 순서는 StringProto.split('').reverse().join('') 이다. 이때 ArrayProto.join()은 배열의 모든 요소를 연결해 하나의 문자열로 만드는 메소드이다.
** 숫자 뒤집기 **
for (let x of arr) {
let res = 0;
while (x) {
let t = x % 10;
res = res * 10 + t;
x = parseInt(x / 10);
}
}
가령 숫자 358에 대해
어떤수 x를 10으로 나눈 나머지 = x의 1의 자릿수 => 8
어떤수를 10으로 나는 몫 = 1의 자리를 제외한 나머지 자릿수 => 35
해당 원리를 이용해 1의 자리수를 추출 -> 곱하기 10 -> 10으로 나눈 몫의 1의 자리수 추출 -> 곱하기 10을 while문으로 반복하면 전체 자릿수가 거꾸로 뒤집힌다.(출력 853) 파이썬에서는 아래와 같이 작성한다.
number = 358
rem = rev = 0
while number >= 1:
rem = number % 10
rev = rev * 10 + rem
number = number // 10
print(rev)
멘토링
현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다.
선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정합니다.
만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 합니다.
M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지 출력하는 프로그램을 작성하세요.
만약 한 줄에 N=4이고, 테스트 결과가 3 4 1 2로 입력되었다면 3번 학생이 1등, 4번 학생이 2등, 1번 학생이 3등, 2번 학생이 4등을 의미합니다.
첫 번째 줄에 짝을 만들 수 있는 총 경우를 출력합니다.
- 입력예제
4 3
3 4 1 2
4 3 2 1
3 1 4 2
- 출력예제
3
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const n = input.shift().split(" ").map(Number);
let nums = [];
for (let i of input) {
nums.push(i.split(" ").map(Number));
}
function solution(n, nums) {
let answer = 0;
let comb = [];
for (let i = 0; i < n[0]; i++) {
for (let j = 0; j < n[0]; j++) {
let isMento = true;
for (let lst of nums) {
if (lst.indexOf(i + 1) >= lst.indexOf(j + 1)) {
isMento = false;
break;
}
}
if (isMento == true) answer++;
}
}
console.log(k);
console.log(answer);
}
solution(n, nums);
- 풀이 해설
4명의 학생 중 멘토, 멘티를 한 명씩 뽑는 4P2의 순열 문제이다. 순열 문제이기 때문에 4명의 학생이 멘토가 되는 경우의 수, 멘티가 되는 경우의 수를 완전탐색해야 한다. 순열의 경우의 수는 4*4-4이다. 편의상 이중for문을 돌려 16가지를 모두 탐색한다.
순열을 구하기 위한 이중for문과 행렬을 탐색하기 위한 이중for문이 필요하다 본 풀이에서는 indexOf 함수를 이용했다. index값이 낮은 경우 낮은 순위이고, 멘토가 되려면 항상 indexOf값이 낮아야 한다.
if문으로 멘토, 멘티 여부를 판별할 때에 break를 쓰지 않으면 30번을 탐색하지만, break를 걸면 14번 탐색으로 탐색 숫자가 줄어든다. 적절한 break를 통해 메모리 사용량을 줄이자.
졸업 선물
선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다.
학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다.
현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요.
선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는 할인에 포함되지 않습니다.
첫 번째 줄에 선생님이 현재 예산으로 선물할 수 있는 최대 학생수를 출력합니다.
선생님 최소한 1개 이상의 상품을 살 수 있는 예산을 가지고 있습니다.
- 입력예제
5 28
6 6
2 2
4 3
4 5
10 3
- 출력예제
4
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const n = input.shift().split(" ").map(Number);
let nums = [];
for (let i of input) {
nums.push(i.split(" ").map(Number));
}
function solution(n, nums) {
let answer;
//금액합이 가장 적은 경우부터 정렬
nums.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));
let many = n[0];
let max_cnt = 0;
//무엇을 할인받을지 정하고, 해당 물건을 곧바로 산다고 가정
for (let i = 0; i < many; i++) {
let money = n[1];
money -= nums[i][0] / 2 + nums[i][1];
cnt = 1;
for (let j = 0; j < many; j++) {
if (j === i) continue;
else if (money - nums[j][0] - nums[j][1] < 0) continue;
else {
money -= nums[j][0] + nums[j][1];
console.log(nums[j][0], nums[j][1]);
cnt++;
console.log(cnt);
}
}
if (cnt > max_cnt) max_cnt = cnt;
}
answer = max_cnt;
console.log(answer);
}
solution(n, nums);
- 풀이 해설
- 배송비와 물품의 값이 적은 순으로 정렬해서 브루트포스로 풀이할 것
- money값은 for문 안에서 매 탐색마다 28로 초기화 할 것
- 중요 50% 할인받을 물건을 정할 것. 그리고 해당 물품을 항상 구매한다고 가정할 것.
money값을 초기화하지 않는 기초적인 실수로 시간이 오래 걸린 문제.
continue를 계속 사용했는데 저렇게 사용해도 되는건지는 잘 모르겠음.
if (j !== i && money - nums[j][0] - nums[j][1] >= 0) {
money -= nums[j][0] + nums[j][1];
console.log(nums[j][0], nums[j][1]);
cnt++;
console.log(cnt);
}
콘틴뉴 구문 이것처럼 수정하였음.
K번째 큰 수
현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다. 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려 고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다. 기록한 값 중 K번째로 큰 수를 출력 하는 프로그램을 작성하세요.
만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값은 22입니다.
첫 줄에 K번째 수를 출력합니다. K번째 수는 반드시 존재합니다.
- 입력예제
10 3
13 15 34 23 45 65 33 11 26 42
- 출력예제
143
- 답안
//인풋을 입력받습니다.
const fs = require("fs");
const { totalmem } = require("os");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const n = input[0].split(" ").map(Number);
const cards = input[1].split(" ").map(Number);
console.log(cards);
function solution(n, cards) {
let answer;
let nc = n[0];
let nk = n[1];
let total_list = [];
for (i = 0; i < nc; i++) {
for (j = i + 1; j < nc - 1; j++) {
for (k = j + 1; k < nc - 2; k++) {
let total = cards[i] + cards[j] + cards[k];
total_list.push(total);
}
}
}
total_list.sort((a, b) => a - b);
answer = total_list[nk - 1];
console.log(answer);
}
solution(n, cards);
- 풀이 해설
조합문제 10C3이다. 조합하는 갯수에 따라 for문이 늘어난다. 이때 for문의 범위를 i, j=i+1, k=j+1과 같이 좁힐 수 있으며, 마찬가지로 끝나는 값 i, j, k도 좁힐 수 있다. (끝나는 값은 좁히지 않아도 결과같이 같다.)
Array.sort(function (a, b) {
a - b;
});
위의 정렬함수는, a가 b보다 작은 경우 음수를 반환하여 순서가 변하지 않는다. 반대로 a가 b보다 큰 경우 양수를 반환하여 원소의 위치가 서로 바뀌게 된다.