알고리즘 공부 5일 차
공부할 것
sort() 아스키코드
29. 3진법 뒤집기
문제 설명
자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
n은 1 이상 100,000,000 이하인 자연수입니다.
해결
function solution(n) {
//n = 45
let answer = 0;
let arr = [];
do {
arr.push(n % 3); //나머지 0 0 2 1
n = Math.floor(n / 3); //몫 15 5 1 0
} while (n > 0);
let l = arr.length;
//0 * 3**3 + 0 * 3**2 + 2 * 3**1 + 1 * 3**0
for (let a of arr) {
answer += a * 3 ** (l - 1);
l--;
}
return answer;
}팀원분 코드(함수로 진법바꾸기)
toString()과 parseInt()의 새로운 사용법을 알게됐다.
function solution(n) {
//n = 45
let answer = [];
let third = n.toString(3); //문자열로 변환, 삼진법으로 변환 '1200'
answer = third.split("").reverse().join(""); // ['0021']
//third.split('') ['1','2','0','0']
//third.split('').reverse() ['0','0','2','1']
return parseInt(answer, 3); //answer 3진법을 10진법으로 변환한다.
//parseInt([...n.toString(3)].reverse().join(""), 3)
}
solution(45);30. 최소직사각형
문제 설명
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.
명함 번호 가로 길이 세로 길이
1 60 50
2 30 70
3 60 30
4 80 40
가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.
모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.
제한사항
sizes의 길이는 1 이상 10,000 이하입니다.
sizes의 원소는 [w, h] 형식입니다.
w는 명함의 가로 길이를 나타냅니다.
h는 명함의 세로 길이를 나타냅니다.
w와 h는 1 이상 1,000 이하인 자연수입니다.
해결
function solution(sizes) {
let answer = 0;
let w = [];
let h = [];
for (let s of sizes) { //세로 값에 더 긴 쪽이 가도록 모두 정렬
s.sort(function (a, b) {
return a - b;
});
}
//sizes =[[ 7, 10 ], [ 3, 12 ], [ 8, 15 ], [ 7, 14 ], [ 5, 15 ]]
for (let i = 0; i < sizes.length; i++) {
for (let j = 0; j < sizes[i].length; j++) {
w.push(sizes[i][0]); //[7, 3, 8, 7, 5] //가로 배열
h.push(sizes[i][1]); //[10, 12, 15, 14, 15] //세로 배열
}
}
answer = Math.max(...w) * Math.max(...h); //각각 비교해 최댓값찾아 곱함
return answer;
}
//입력 테스트
solution([
[10, 7],
[12, 3],
[8, 15],
[14, 7],
[5, 15],
]);
31. 같은 숫자는 싫어
문제 설명
배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,
arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.
제한사항
배열 arr의 크기 : 1,000,000 이하의 자연수
배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
해결
그냥 뒤의 요소와 불일치하면 answer에 push
function solution(arr) {
let answer = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== arr[i + 1]) {
answer.push(arr[i]);
}
}
return answer;
}
solution([4, 4, 4, 3, 3]);
실패
효율성 0점 맞음 arr길이가 최대 백만개 ㅋㅋㅋㅋㅋㅋ
function solution(arr) {
let answer = [];
let delIndex = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] === arr[i + 1]) {
//제거할 값의 인덱스를 찾는다 [ 0, 1, 3 ]
delIndex.push(i);
}
}
for (let index of delIndex) {
//arr에서 해당 인덱스 값을 []로 바꾼다 (그냥 제거하면 인덱스가 바뀌므로 교체 )
arr.splice(index, 1, []);
//[ [], 4, 4, 3, 3 ]
//[ [], [], 4, 3, 3 ]
//[ [], [], 4, [], 3 ]
}
arr = arr.join("").split(""); //공백 []을 제거해 다시 쪼갠다 [ '4', '3' ]
for (let a of arr) {
//요소를 숫자로 변환해 넣는다.
answer.push(parseInt(a)); //[4,3]
}
return answer;
}
solution([4, 4, 4, 3, 3]);32. 두 개 뽑아서 더하기
문제 설명
정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
numbers의 길이는 2 이상 100 이하입니다.
numbers의 모든 수는 0 이상 100 이하입니다.
해결
function solution(numbers) {
let answer = [];
let arr = [];
for (let i = 0; i < numbers.length; i++) {
//두 인덱스를 더해 나오는 모든 조합을 구한다.
for (let j = 0; j < numbers.length; j++) {
if (i !== j) {
//자기자신끼린 더하지 않도록 한다.
arr.push(numbers[i] + numbers[j]);
}
}
}
arr.sort(function (a, b) {
//오름차순으로 정리한다
return a - b;
});
for (let i = 0; i < arr.length; i++) {
//유일값만 answer에 추가한다.
if (arr[i] !== arr[i + 1]) {
answer.push(arr[i]);
}
}
return answer;
}Set()을 사용해 중복값을 쉽게 제거한다
function solution(numbers) {
let answer = [];
let arr = [];
for (let i = 0; i < numbers.length; i++) {
//두 인덱스를 더해 나오는 모든 조합을 구한다.
for (let j = 0; j < numbers.length; j++) {
if (i !== j) {
//자기자신끼린 더하지 않도록 한다.
arr.push(numbers[i] + numbers[j]);
}
}
}
answer = [...new Set(arr)]; //전개 연산자와 Set을 이용해 유일값만 남긴다.
answer.sort(function (a, b) {
//오름차순으로 정리한다
return a - b;
});
return answer;
}팀원분 코드
answer에 이미 넣은 요소는 넣지 않는 것으로 중복값을 배제한다.
function solution(numbers) {
let answer = [];
for (let i = 0; i < numbers.length; i++) {
// i를 numbers의 길이만큼 반복
for (let j = i + 1; j < numbers.length; j++) {
// j를 i+1길이만큼 반복
let plus = numbers[i] + numbers[j]; // plus는 number의 [i]+[j]
if (!answer.includes(plus)) answer.push(plus); // 만일 answer에 includes(plus)가 없으면 answer에 push
}
}
answer.sort((a, b) => a - b); // answer 오름차순으로 정렬
return answer;
}33. 로또의 최고 순위와 최저 순위
뭐라 말은 길지만, 지워진 수가 다 맞았을 때의 등수와 지워진 수가 전부 틀렸을 때의 등수를 각각 구하라는 얘기
문제 설명
로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1
로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다.
알아볼 수 없는 번호를 0으로 표기하기로 하고, 민우가 구매한 로또 번호 6개가 44, 1, 0, 0, 31 25라고 가정해보겠습니다. 당첨 번호 6개가 31, 10, 45, 1, 6, 19라면, 당첨 가능한 최고 순위와 최저 순위의 한 예는 아래와 같습니다.
순서와 상관없이, 구매한 로또에 당첨 번호와 일치하는 번호가 있으면 맞힌 걸로 인정됩니다.
알아볼 수 없는 두 개의 번호를 각각 10, 6이라고 가정하면 3등에 당첨될 수 있습니다.
3등을 만드는 다른 방법들도 존재합니다. 하지만, 2등 이상으로 만드는 것은 불가능합니다.
알아볼 수 없는 두 개의 번호를 각각 11, 7이라고 가정하면 5등에 당첨될 수 있습니다.
5등을 만드는 다른 방법들도 존재합니다. 하지만, 6등(낙첨)으로 만드는 것은 불가능합니다.
민우가 구매한 로또 번호를 담은 배열 lottos, 당첨 번호를 담은 배열 win_nums가 매개변수로 주어집니다. 이때, 당첨 가능한 최고 순위와 최저 순위를 차례대로 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
제한사항
lottos는 길이 6인 정수 배열입니다.
lottos의 모든 원소는 0 이상 45 이하인 정수입니다.
0은 알아볼 수 없는 숫자를 의미합니다.
0을 제외한 다른 숫자들은 lottos에 2개 이상 담겨있지 않습니다.
lottos의 원소들은 정렬되어 있지 않을 수도 있습니다.
win_nums은 길이 6인 정수 배열입니다.
win_nums의 모든 원소는 1 이상 45 이하인 정수입니다.
win_nums에는 같은 숫자가 2개 이상 담겨있지 않습니다.
win_nums의 원소들은 정렬되어 있지 않을 수도 있습니다.
해결
function solution(lottos, win_nums) {
let answer = [];
let eq_count = 0; //일치 개수
let zero = 0; //지워진 수(0)의 개수
const rank = [6, 6, 5, 4, 3, 2, 1]; //순위 책정표를 배열로 정리
//인덱스는 맞은 개수 값은 등수를 의미. 즉, rank[0] =6이면 0개 맞추면 6등이란 뜻
for (let my of lottos) {
if (my === 0) {
//0이 몇 개인지
zero++;
}
if (win_nums.includes(my)) {
//win_numbers에 lottos의 요소가 몇 개 인지
eq_count++;
}
}
answer = [rank[eq_count + zero], rank[eq_count]];
return answer;
}34. 모의고사
문제 설명
수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.
1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...
1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한 조건
시험은 최대 10,000 문제로 구성되어있습니다.
문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.
해결
뭔 삽질을 했는지 모를 코드
정답배열 인덱스가 각 수포자의 찍기배열의 배수일 때, 수포자 인덱스를 0부터 다시시작하여 비교한다. 그냥 index = j%test[i].length 이렇게 하면 나머지가 알아서 0부터 다시 도는데 ㅠㅠ .
게다가 이 수포자 셋을 한 번에 계산한다고 찍기 배열들을 배열 하나에다 때려넣었다
(맞추긴 했다...)
function solution(arr) {
let answer = [];
let test = [
[1, 2, 3, 4, 5],
[2, 1, 2, 3, 2, 4, 2, 5],
[3, 3, 1, 1, 2, 2, 4, 4, 5, 5],
];
let count_arr = []; //맞은 개수 담는 배열, 인덱스+1이 수포자 번호다.
let max = 0; //위 배열의 최댓값
for (let i = 0; i < test.length; i++) {
let count = 0; //맞은개수
let index = 0;
for (let j = 0; j < arr.length; j++) {
index = j % test[i].length ? index + 1 : 0; //정답배열의 인덱스(j)가 수포자배열로 나누어떨어지면 index는 0 아니면 1씩 증가한다.
//그냥 index = j%test[i].length이렇게 쓰면 되는 거였다...
if (arr[j] === test[i][index]) {
//맞은 개수를 체크한다.
count++;
}
}
count_arr.push(count); //맞은개수를 배열에 넣는다.
}
console.log(count_arr);
max = Math.max(...count_arr); //맞은개수들의 가장큰 값을 구한다
for (let i = 0; i < count_arr.length; i++) {
if (count_arr[i] === max) {
//최고 득점 수포자번호를 answer배열에 담는다.
answer.push(i + 1);
}
}
return answer.sort(); //answer를 오름차순 정렬해 리턴한다.(바로 위 for문에서 i순으로 push했으니 정렬 안 해도 되는 듯)
}다른 사람의 풀이
프로그래머스에서 찾아냄
나랑 해결 순서는 비슷 ㅠ
function solution(answers) {
var answer = [];
const man1 = [1, 2, 3, 4, 5];
const man2 = [2, 1, 2, 3, 2, 4, 2, 5];
const man3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
let count = [0, 0, 0];
for (let i = 0; i < answers.length; i++) {
if (answers[i] == man1[i % man1.length]) count[0]++;
if (answers[i] == man2[i % man2.length]) count[1]++;
if (answers[i] == man3[i % man3.length]) count[2]++;
}
const max = Math.max(count[0], count[1], count[2]);
for (let i = 0; i < count.length; i++) {
if (max == count[i]) answer.push(i + 1);
}
return answer;
}팀원분 코드
function solution(answers) {
let pattern1 = "12345";
let pattern2 = "21232425";
let pattern3 = "3311224455";
let pattern1Score = checking(pattern1);
let pattern2Score = checking(pattern2);
let pattern3Score = checking(pattern3);
let grade = grading(pattern1Score, pattern2Score, pattern3Score);
function checking(pattern) {
//각자 몇 개 맞췄는지 체크하는 함수
let count = 0;
pattern = pattern
.repeat(Math.ceil(answers.length / pattern.length))
.split(""); // 2, 2-1번 로직
for (let i = 0; i < answers.length; i++) {
if (answers[i] === +pattern[i]) {
count++;
}
}
return count;
}
function grading(score1, score2, score3) {
//최고 득점자를 가리는 함수
let king = [];
let arr = [score1, score2, score3];
arr.sort(function (a, b) {
return b - a;
});
if (arr[0] === score1) king.push(1);
if (arr[0] === score2) king.push(2);
if (arr[0] === score3) king.push(3);
return king;
}
return grade;
}36. 문자열 내림차순으로 배치하기
문제 설명
문자열 s에 나타나는 문자를 큰 것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요.
s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다.
제한 사항
str은 길이 1 이상인 문자열입니다.
해결
본래 유니코드에서 대문자는 소문자보다 작은 것으로 취급되는 모양
sort(function(a,b){return b-a}로는 내림차순으로 변경되지 않았는데 문자열은 방법이 따로 있는 듯하다(공부할 것). 그래서 reverse()로 뒤집었다.
function solution(s) {
let answer = [];
answer = s.split('')
return answer.sort().reverse().join("")
}(+)내림차순 해결함.
방법이 따로 있다긴 보단 숫자만 sort안의 compareFunction을 줄여 쓸 수 있었네
function solution(s) {
let answer = [];
answer = s.split('').sort(function(a,b){
if(a>b) return -1;
if(a<b) return 1;
return 0;
}).join('')
return answer
}
39. 시저 암호
문제 설명
어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다. 예를 들어 "AB"는 1만큼 밀면 "BC"가 되고, 3만큼 밀면 "DE"가 됩니다. "z"는 1만큼 밀면 "a"가 됩니다. 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성해 보세요.
제한 조건
공백은 아무리 밀어도 공백입니다.
s는 알파벳 소문자, 대문자, 공백으로만 이루어져 있습니다.
s의 길이는 8000이하입니다.
n은 1 이상, 25이하인 자연수입니다.
해결
java char타입에서 'a'+1 =='b'일텐데. 아스키 코드 순으로 js도 이런거 있을건데 모름...(공부할 것) 결국, 알파벳을 다 침
26자를 두 번 치기 싫어서 대문자 문자열만 만들었는데, 보니까 이렇게 일일이 친 사람들은 보통 소문자 문자열도 만들더라.
function solution(s, n) {
const alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
let answer = "";
for (let a of s) {
if (a === " ") {
//공백엔 공백을 저장
answer += " ";
} else {
let alpha_i = alpha.indexOf(a.toUpperCase()); //a가 alpha에선 몇 인덱스에 있는지(대소문자 구부없이 확인)
if (alpha.includes(a)) {
//대문자의 경우
answer += alpha[(alpha_i + n) % 26]; //(alpha_i +n )은 n만큼 밀은 인덱스, alpha 문자열 밖으로 나가면 0부터 다시 시작하므로 %26한다.
} else if (alpha.includes(a.toUpperCase())) {
//소문자의 경우 대문자로 변환해 검사하고 다시 소문자로 바꾼다.
answer += alpha[(alpha_i + n) % 26].toLowerCase();
}
}
}
return answer;
}다른 사람 코드
프로그래머스에서 찾음
function solution(s, n) {
let upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
let lower = "abcdefghijklmnopqrstuvwxyz";
let answer = "";
for (let i = 0; i < s.length; i++) {
let text = s[i];
if (text == " ") {
answer += " ";
} else {
let textArr = upper.includes(text) ? upper : lower;
let index = textArr.indexOf(text) + n;
answer += textArr[index % 26];
}
}
return answer;
}35, 37, 38, 40
못함...내일로
Author And Source
이 문제에 관하여(알고리즘 공부 5일 차), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@doyeon11/알고리즘-공부-5일-차저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
