1. 자릿수의 합
N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력
하는 프로그램을 작성하세요. 자릿수의 합이 같은 경우 원래 숫자가 큰 숫자를 답으로 합니다.
만약 235 와 1234가 동시에 답이 될 수 있다면 1234를 답으로 출력해야 합니다.
function solution(numArr) {
let answer,
max = Number.MIN_SAFE_INTEGER;
for (let x of numArr) {
let sum = 0,
tmp = x;
// tmp 128 / tmp%10 8
// tmp 12 / tmp%10 2
// tmp 1 / tmp%10 1
// tmp 0 / break;
while (tmp) {
sum += tmp % 10;
tmp = Math.floor(tmp / 10);
}
if (sum > max) {
max = sum;
answer = x; // x=원본
} else if (sum === max) {
// 128 < 137
if (x > answer) answer = x;
}
}
return answer;
}
function solution1(numArr) {
let answer,
max = Number.MIN_SAFE_INTEGER;
for (let x of numArr) {
let sum = x
.toString()
.split('')
.reduce((a, b) => +a + +b, 0);
if (sum > max) {
max = sum;
answer = x; // x=원본
} else if (sum === max) {
// 128 < 137
if (x > answer) answer = x;
}
}
return answer;
}
console.log(solution([128, 460, 603, 40, 521, 137, 123])); // 137
console.log(solution1([128, 460, 603, 40, 521, 137, 123])); // 137
function solution3(arr) {
let answer = [];
const strArr = arr.map((i) => String(i));
for (let i = 0; i < strArr.length; i++) {
let sum = 0;
for (let j = 0; j < strArr[i].length; j++) {
sum += Number(strArr[i][j]);
}
answer.push([+strArr[i], +sum]);
sum = 0;
}
return Math.max(
...answer
.sort((a, b) => b[1] - a[1])
.filter(([_, sum]) => sum === answer[0][1])
.map(([num, _]) => num)
);
}
console.log(solution3([128, 460, 603, 40, 521, 137, 123])); // 1372. 뒤집은 소수
N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하
는 프로그램을 작성하세요. 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출
력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다. 첫 자리부터의 연속된 0은 무시한다.
function isPrime(num) {
if (num === 1) return false;
for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
if (num % i === 0) return false;
}
return true;
}
function mySolution(arr) {
let answer = [];
for (let x of arr) {
const reverseNum = Number(String(x).split('').reverse().join(''));
if (isPrime(reverseNum)) answer.push(reverseNum);
}
return answer;
}
function solution(arr) {
let answer = [];
for (let x of arr) {
let res = 0;
while (x) {
let t = x % 10;
res = res * 10 + t;
x = parseInt(x / 10);
}
if (isPrime(res)) answer.push(res);
}
return answer;
}
console.log(mySolution([32, 55, 62, 20, 250, 370, 200, 30, 100])); // 23 2 73 2 3
console.log(solution([32, 55, 62, 20, 250, 370, 200, 30, 100])); // 23 2 73 2 3뒤집힌 숫자를 Number(String(x).split('').reverse().join('')) 이것보다 더 직관적이게? 만들 수 있는 방법이 있나 궁금하고, isPrime 함수를 밖에다 구현할 생각을 못 해서 for문 안에서 소수를 어떻게 만들지 머리 아팠다
3. 멘토링
현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니
다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의
수학공부를 도와주는 것입니다.
선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정합니다.
만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서
모두 B학생보다 등수가 앞서야 합니다.
M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지
출력하는 프로그램을 작성하세요.
// A 멘토 - B 멘티
// A 학생은 M 번의 수학테스트에서 모두 B 학생보다 등수가 앞서야 함.
// 총 경우의 수는 16가지겠구나. 나는 이 16가지를 모두 확인해 봐야겠다 => 블루투포스
function solution(test) {
let answer = 0; // 멘토 멘티가 될 수 있는 횟수
const [M, N] = [test.length, test[0].length];
for (let i = 1; i <= N; i++) {
for (let j = 1; j <= N; j++) {
// 총 16가지 경우의 수 (i 멘토 - j 멘티)
// i 학생이 멘토, j 학생의 멘티가 되는 경우는
// i가 j를 3번의 수학 테스트에서 모두 등수가 앞서야 함
let cnt = 0;
for (let k = 0; k < M; k++) {
let pi = (pj = 0);
// s 등수
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;
}
function solution1(arr) {
let answer = [];
for (let i = 0; i < arr.length; i++) {
let nTest = arr[i];
if (i === 0) {
for (let x = 0; x < nTest.length - 1; x++) {
for (let y = x + 1; y < nTest.length; y++) {
answer.push([nTest[x], nTest[y]]);
}
}
} else {
let prevArr = [...answer];
answer = [];
for (let x = 0; x < prevArr.length; x++) {
let first = prevArr[x][0];
let second = prevArr[x][1];
if (nTest.indexOf(first) < nTest.indexOf(second)) {
answer.push([first, second]);
}
}
}
}
return answer.length;
}
function solution2(test) {
let answer = 0;
let flag = 0;
let m = test[0].length;
let n = test.length;
// 첫번째 시험에서 도출되는 총 경우의 수
for (let i = 1; i < m; i++) answer += i;
for (let i = 0; i < m - 1; i++) {
for (let j = i + 1; j < m; j++) {
flag = 0;
for (let k = 1; k < n; k++) {
if (test[k].indexOf(test[0][i]) > test[k].indexOf(test[0][j])) {
flag = 1;
break;
}
}
if (flag) answer--;
}
}
return answer;
}
const arr = [
[3, 4, 1, 2],
[4, 3, 2, 1],
[3, 1, 4, 2],
];
console.log(solution(arr)); // 3
console.log(solution1(arr)); // 3
console.log(solution2(arr)); // 34. 졸업선물
선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다.
학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라
고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다.
현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요.
선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는
할인에 포함되지 않습니다.
✏ 입력 설명
첫 번째 줄에 반 학생수 N(1<=N<=1000)과 예산 M(1<=M<=100,000,000)이 주어진다.
두 번째 줄부터 N줄에 걸쳐 각 학생들이 받고 싶은 상품의 가격과 배송비가 입력됩니다.
상품가격과 배송비는 각각 100,000을 넘지 않습니다. 상품가격은 짝수로만 입력됩니다.
✏ 출력 설명
첫 번째 줄에 선생님이 현재 예산으로 선물할 수 있는 최대 학생수를 출력합니다.
선생님 최소한 1개 이상의 상품을 살 수 있는 예산을 가지고 있습니다.
// 그냥 다 해보는 것. 모든 경우를 다 탐색하는 것 => 완전 탐색
// 이 문제에서 모든 경우는? 어떤 상품을 할인받을지
// 1. 정렬 -> 28 - 배송비+상품가격 -> 남은 금액에서?
// 2 2 -> 4 3 -> 4 5 -> ... 이걸 할인받는다. 생각하고 다해보고
// 모든 상품을 다 할인받았다 가정하고 하는 수밖에 없음
// => 이런 생각을 해내야 한다..
function solution(M, products) {
let answer = 0; // 몇 개 살 수 있는지 최대개수 카운팅
let N = products.length;
products.sort((a, b) => a[0] + a[1] - (b[0] + b[1])); // 오름차순 정렬
// 총비용으로정렬됨 [ [ 2, 2 ], [ 4, 3 ], [ 4, 5 ], [ 6, 6 ], [ 10, 3 ] ]
for (let i = 0; i < N; i++) {
// i번째 상품을 할인받는다
// 상품 가격은 항상 짝수로만 입력되므로 -> /2
let leftMoney = M - (products[i][0] / 2 + products[i][1]); //남은예산=>원래예산-(상품가격/2+배송비)
let cnt = 1; // 몇개까지살수있는지카운팅
for (let j = 0; j < N; j++) {
// 밑에 if가 참이 아닐 때 카운팅 되진 않겠지만 학생수가 많으면 계속 돌아서 break
// j번째 상품을 사는 총 비용이 남은 예산보다 크면 -> break
if (j !== i && products[j][0] + products[j][1] > leftMoney) break;
// 정렬된 순서(최소비용)대로 남은 금액으로 살 수 있는 것들 다 사기
// "갯수가 중요"하니 비용이 작은 것들로 사야 최대 갯수로 많이 살 수 있음
// i 는 할인된 상품이라 사면 안됨
// && 사려고 하는 j 번째 상품 총비용 금액이 남은 예산보다 작거나 같아야 함
if (j !== i && products[j][0] + products[j][1] <= leftMoney) {
leftMoney -= products[j][0] + products[j][1];
cnt++; // 상품을 하나 더 샀다
}
}
// j가 다 돌고
answer = Math.max(answer, cnt);
}
return answer;
}
const param = {
m: 28,
arr: [
[6, 6], // 이 상품이 할인받는다 해보고
[2, 2], // 이 상품이 할인받는다 해보고
[4, 3], // ... 다해보고
[4, 5],
[10, 3],
],
};
const param1 = {
m: 41,
arr: [
[8, 6],
[2, 2],
[4, 3],
[4, 5],
[12, 1],
],
};
const param2 = {
m: 596,
arr: [
[6, 331],
[4, 251],
[8, 675],
[5, 214],
[10, 735],
[5, 996],
[9, 609],
[9, 371],
[8, 377],
[5, 707],
[7, 907],
[6, 433],
[9, 737],
[8, 796],
[4, 265],
[3, 484],
[8, 488],
[8, 191],
[9, 232],
[4, 195],
],
};
const param3 = {
m: 41,
arr: [
[8, 6],
[2, 2],
[4, 3],
[4, 5],
[12, 1],
],
};
console.log(solution(param.m, param.arr)); // 4
console.log(solution(param1.m, param1.arr)); // 5
console.log(solution(param2.m, param2.arr)); // 2
console.log(solution(param3.m, param3.arr)); // 5
function getPresentStudent(maxMoney, product) {
let answer = 0;
product.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));
for (let i = 0; i < product.length; i++) {
let buySaleLeftMoney = maxMoney - (product[i][0] * 0.5 + product[i][1]);
let count = 1;
for (let j = 0; j < product.length; j++) {
if (j === i) continue;
buySaleLeftMoney -= product[j][0] + product[j][1];
count++;
if (buySaleLeftMoney <= 0) {
answer = count;
break;
}
}
}
return answer;
}
console.log(getPresentStudent(param.m, param.arr)); // 4
console.log(getPresentStudent(param1.m, param1.arr)); // 5
console.log(getPresentStudent(param2.m, param2.arr)); // 2
console.log(getPresentStudent(param3.m, param3.arr)); // 55. 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번째 수는 반드시 존재합니다.
function solution(input = '10 3\n13 15 34 23 45 65 33 11 26 42') {
const [_, nums] = input.split('\n');
const [N, K] = _.split(' ');
const arr = nums.split(' ').map(Number); // ❓
let set = 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++) {
set.add(arr[i] + arr[j] + arr[k]);
}
}
}
// Array.from() 함수는 유사배열객체나 반복가능객체를 얕은 복사하여 새로운 배열을 만듦
// 유사배열객체(array-like object) : length 속성과 index element를 가지는 객체
// 반복가능객체(iterable object) : 배열을 일반화한 객체 ex)Map, Set
return Array.from(set).sort((a, b) => b - a)[K - 1];
}
console.log(solution()); // 143
function solution1(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(solution1(10, 3, arr)); // 143마무리
완전 탐색은 다른 파트보다 강의를 몇 번씩이나 더 들었는데 아직 혼자선 이 문제를 풀려면 이 경우를 다 탐색해야겠지? 하는 등의 방법을 못 찾겠다.. 그래서 스터디도 다음 주로 미뤄졌고ㅜㅜ 완탐도 그렇고 알고리즘 문제 잘 풀고 싶다 그러니까 뭐 더 노력해야지 어쩌겠음 😭
꾸준히 자유롭게 즐겁게