안녕하세요
프로그래머스 JS 완전탐색 [6/7] 본문
최소직사각형 문제 보기 (5)
문제 풀이
지갑의 긴 길이를 가로로, 짧은 길이를 세로로 놓는다고 할 때,
카드도 마찬가지로 긴 길이를 가로로, 짧은 길이를 세로로 둔다.
카드의 가로가 지갑의 가로보다 길면 지갑의 길이를 카드의 가로로 바꾼다.
카드의 세로가 지갑의 세로보다 길면 지갑의 길이를 카드의 세로로 바꾼다.
모든 카드에 대해 확인한다.
const solution = (cards) => {
let width = 0;
let height = 0;
cards.forEach((card) => {
const [w, h] = card;
const bigger = Math.max(w, h);
const smaller = Math.min(w, h);
if (width < bigger) width = bigger;
if (height < smaller) height = smaller;
});
return width * height;
};
solution([
[14, 4],
[19, 6],
[6, 16],
[18, 7],
[7, 11],
]);모의고사 Level 1 문제 보기 (10)
문제 풀이
1. 학생별로 찍는 순서를 배열로 만든다.
2. [ i % a.length ] 와 같이 길이의 나머지를 이용하여 값의 일치를 비교하고, 정답을 맞춘 횟수를 기록한다.
3. 최고 점수를 Math.max() 로 찾는다.
4. 최고 점수를 지닌 학생의 index를 반환한다.
const solution = (answer) => {
let count = Array.from({ length: 3 }).fill(0);
const a = [..."12345"];
const b = [..."21232425"];
const c = [..."3311224455"];
answer.forEach((num, i) => {
if(a[i % a.length] == num) count[0]++;
if(b[i % b.length] == num) count[1]++;
if(c[i % c.length] == num) count[2]++;
});
const highScore = Math.max(...count);
const result = [];
count.forEach((num, i) => {
if (num === highScore) result.push(i + 1);
});
return result;
};
solution([1, 3, 2, 4, 2]);소수 찾기 Level 2 문제 보기 (30)
문제 풀이
1. 숫자 조각을 이용해 만들 수 있는 모든 숫자 조합을 만든다.
- "1", "01", "001" 처럼 0이 앞에 조합된 숫자는 모두 1 이다.
2. 숫자 조합에 대해서 소수 판별을 한다.
- 소수를 판별할 때 짝수는 반드시 소수가 아니다.
num % 2 === 0 인 경우에 대해서 선리턴을 해주고,
for 문의 i 를 2씩 증가시키며 찾으면 소수 판별 시행을 반으로 줄일 수 있다.
const isPrime = (num) => {
if (num === 2) return true;
if (num === 1 || num % 2 === 0) return false;
for (let i = 3; i * i <= num; i += 2) {
if (num % i === 0) return false;
}
return true;
};
function solution(numbers) {
const nums = [...numbers];
const permutationSet = new Set();
const getPermutation = (arr, i, pick) => {
if (i === pick) {
const number = Number(arr.slice(0, i).join(""));
if (isPrime(number)) {
permutationSet.add(number);
}
}
for (let j = i; j < nums.length; j++) {
[arr[i], arr[j]] = [arr[j], arr[i]];
getPermutation(arr, i + 1, pick);
[arr[i], arr[j]] = [arr[j], arr[i]];
}
};
for (let pick = 1; pick <= nums.length; pick++) {
getPermutation(nums, 0, pick);
}
return permutationSet.size;
}카펫 Level 2 문제 보기 (10)
문제 포인트
- yellow는 가로*세로 형태의 격자이다
- brown은 (가로+2) * (세로+2) 에서 겹치는 모서리 부분을 빼주면 된다. (-4)
가로1┌ ─ ┐
세로1│ │세로2
가로2└ ─ ┘
문제 풀이
1. 두 수를 곱해 yellow를 만들 수 있는 x,y 를 구한 배열을 만든다. (약수 구하기)
2. 약수 배열에서 (x+2) + (y+2) * 2 - 4 가 brown이 되는 수를 찾는다.
const solution = (brown, yellow) => {
// 두 수를 곱해 yellow를 구성할 수 있는 수를 구한다 (약수 구하기)
const yellowDivisors = [];
for (let i = 0; i * i <= yellow; i++) {
if (yellow % i === 0) {
yellowDivisors.push(i);
yellowDivisors.push(~~(yellow / i));
}
}
for (let i = 0; i < yellowDivisors.length; i += 2) {
const [x, y] = yellowDivisors.slice(i, i + 2); // yellow의 약수
if ((x + 2) * 2 + (y + 2) * 2 - 4 === brown) {
return [y, x].map((item) => item + 2); // 각각의 수에 +2 해주면 카펫의 가로와 세로가 된다.
}
}
};피로도 Level 2 문제 보기 (15)
문제 포인트
- 모든 던전 탐색 방법을 만들기
- 최소 필요 피로도라는 입장 조건을 지켜야만 던전에 입장 할 수 있다는 조건
문제 풀이
1. 던전을 탐색할 수 있는 모든 가짓수를 만듭니다.
- 던전 최대 길이만큼 만들어 놓고, 입장을 할 수 있는지 없는지는 그 다음에 살핍니다.
2. while문으로 던전 플랜이 남지 않을때까지 진행합니다. const dungeon = allPlans.pop();
- 던전에 입장이 가능하다면 입장을 하고, if (stamina >= min)
- 던전 입장 카운트 ++, 소모 피로도 -- 해줍니다.
const solution = (k, dungeons) => {
// 필요 피로도가 80 minimum
// 소모 피로도가 20--
const allPlans = []; // 던전 탐색할 수 있는 모든 플랜
const dungeonLength = dungeons.length; // 던전 길이
const dfs = (array, i) => {
if (i === dungeonLength) {
// 던전 길이만큼 플랜에 추가했다면
allPlans.push([...array]); // 해당 플랜을 던전 탐색 방법 추가
return;
}
// 모든 가짓수 탐색
for (let j = i; j < dungeonLength; j++) {
[array[i], array[j]] = [array[j], array[i]];
dfs(array, i + 1);
[array[i], array[j]] = [array[j], array[i]];
}
};
dfs(dungeons, 0);
let result = 0;
while (allPlans.length) {
// 플랜이 남지 않을 때까지 진행
let stamina = k; // 현재 피로도
let count = 0; // 탐색 횟수
const dungeon = allPlans.pop(); // 현재 플랜
for (let room of dungeon) {
const [min, use] = room; // [방에 입장하기 위한 최소 피로도, 사용할 피로도]
if (stamina >= min) {
// 입장할 수 있다면,
stamina -= use; // 피로도를 소모하고
count++; // 탐색 횟수를 +1 한다.
}
}
result = Math.max(result, count);
}
return result;
};
solution(80, [
[80, 20],
[50, 40],
[30, 10],
]);
전력망을 둘로 나누기 Level 2 문제 보기 (*)
모음 사전 Level 2 문제 보기 (10)
문제 포인트
A, AA, AAA, AAAA, AAAAA,
AAAAE, AAAAI, AAAAO, AAAAU,
AAAE ... 의 규칙은?
AEIOU를 각각 최대 5개씩 이용하여 최대 길이 5의 문자열을 만든다.
생성한 문자열들에 대해서 sort()로 정렬하면 볼 수 있는 순서이다.
이 규칙을 모르고 직접 만든 적이 있다.
마지막이 U면... U를 pop하고 어쩌고저쩌고... 그렇게 오랜 시간 걸려 구현했더니 실행 시간이 너무 오래 걸렸었다.
규칙을 알면 쉬운데 모르면 어렵다.
문제 풀이
1. 만들 수 있는 모든 문자열을 만든다.
2. sort()로 정렬한다.
3. indexOf(word) 로 찾는 문자열의 인덱스를 찾고, +1 을 하여 반환한다.
const solution = (word) => {
const words = []; // 알파벳으로 조합가능한 모든 경우
const alphabets = "AEIOU"; // 알파벳 규칙
const getPermutation = (string, pick) => {
if (string.length === pick) { // 문자열의 길이가 1,2,3,4,5 에 도달하면 반환
words.push(string);
return;
}
for (let i = 0; i < alphabets.length; i++) {
getPermutation(string + alphabets[i], pick); // ""에 A,E,I,O,U 조합
}
};
for (let pick = 1; pick <= 5; pick++) {
getPermutation("", pick); // n개의 문자열 고르기
}
return words.sort().indexOf(word) + 1; // 해당 문자열의 번호 반환
};