Programmers Problem(lev.2) : 카펫
- Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
-
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
- 제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
- 제한사항
-
입출력 예
| brown | yellow | return |
|---|---|---|
| 10 | 2 | [4, 3] |
| 8 | 1 | [3, 3] |
| 24 | 24 | [8, 6] |
Solution
function solution(brown, yellow) {
let answer = [];
for (let i = 1; i <= yellow; i++) {
if (yellow % i === 0) {
const quoient = yellow / i;
const total = (i + 2) * (quoient + 2);
const isValid = total - yellow === brown;
if (isValid) {
answer.push(i + 2, quoient + 2);
break;
}
}
}
answer.sort((a, b) => b - a);
return answer;
}Programmers Problem(lev.2) : 모음사전
-
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
-
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
- 제한사항
- word의 길이는 1 이상 5 이하입니다.
- word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
- 제한사항
-
입출력 예
| word | result |
|---|---|
| "AAAAE" | 6 |
| "AAAE" | 10 |
| "I" | 1563 |
| "EIO" | 1189 |
Solution
function solution(word) {
let answer = 0;
const numberOfAlphabet = 5;
const numberOfCases = numberOfAlphabet + numberOfAlphabet**2 + numberOfAlphabet**3 + numberOfAlphabet**4 + numberOfAlphabet**5;
for (let digit = 1; digit <= word.length; digit++) {
let index = digit - 1;
let interval = Math.floor(numberOfCases / Math.pow(numberOfAlphabet, digit));
if (word[index] === 'A') {
answer += 1;
} else if (word[index] === 'E') {
answer += interval * 1 + 1;
} else if (word[index] === 'I') {
answer += interval * 2 + 1;
} else if (word[index] === 'O') {
answer += interval * 3 + 1;
} else {
answer += interval * 4 + 1;
}
}
return answer;
}-
풀이
- 경우의 수
- 문자열 : "A", "E", "I", "O", "U" => 5개
- 사전에 들어갈 수 있는 문자열의 길이 : 5개
- 모든 경우의 수 : 5 + 5^2 + 5^3 + 5^4 + 5^5 = 3905개
- 각 문자의 간격
- 자리 수의 간격 = 모든 경우의 수 / 문자열 길이의 경우의 수
- 1 번째 자리의 경우 간격 = 3905 / (5^1) = 781
- 2 번째 자리의 경우 간격 = 3905 / (5^2) = 156
- 3 번째 자리의 경우 간격 = 3905 / (5^3) = 31
- 4 번째 자리의 경우 간격 = 3905 / (5^4) = 6
- 5 번째 자리의 경우 간격 = 3905 / (5^1) = 1
- 경우의 수
-
입출력 예
// "AAAAE"
A : 1
A : 1 + 1 = 2
A : 2 + 1 = 3
A : 3 + 1 = 4
E : 4 + 1 * 1 + 1 = 6
// "AAAE"
A : 1
A : 1 + 1 = 2
A : 2 + 1 = 3
E : 3 + 6 * 1 + 1 = 10
// "I"
I : 781 * 2 + 1 = 1563
// "EIO"
E : 781 + 1 = 782
I : 782 + 156 * 2 + 1 = 1095
O : 1095 + 31 * 3 + 1 = 1189Programmers Problem(lev.2) : 전력망을 둘로 나누기
-
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
-
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
- 제한사항
- n은 2 이상 100 이하인 자연수입니다.
- wires는 길이가 n-1인 정수형 2차원 배열입니다.
- wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
- 1 ≤ v1 < v2 ≤ n 입니다.
- 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
- n은 2 이상 100 이하인 자연수입니다.
- 제한사항
-
입출력 예
| n | wires | result |
|---|---|---|
| 9 | [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] | 3 |
| 4 | [[1,2],[2,3],[3,4]] | 0 |
| 7 | [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] | 1 |
Solution
function solution(n, wires) {
let answer = n;
const wireMap = new Map();
for (let i = 0; i < wires.length; i++) {
const [startNode, endNode] = wires[i];
const startNodeNeighbors = wireMap.get(startNode);
const endNodeNeighbors = wireMap.get(endNode);
wireMap.set(startNode, startNodeNeighbors ? [...startNodeNeighbors, endNode] : [endNode]);
wireMap.set(endNode, endNodeNeighbors ? [...endNodeNeighbors, startNode] : [startNode]);
}
const getDiffBetweenWires = (severedWireIndex) => {
const leftWires = new Set();
const [startWire, severedWire] = wires[severedWireIndex];
leftWires.add(startWire);
for (let startNode of leftWires.values()) {
wireMap.get(startNode).forEach((endNode) => {
if (endNode !== severedWire) {
leftWires.add(endNode);
}
});
}
return Math.abs(n - leftWires.size * 2);
}
for (let severedWireIndex = 0; severedWireIndex < wires.length; severedWireIndex++) {
answer = Math.min(getDiffBetweenWires(severedWireIndex), answer);
}
return answer;
}Programmers Problem(lev.2) : 소수 찾기
- 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
- 각 종이 조각에 적힌 숫자가 적힌 문자열
numbers가 주졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.- 제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
- 제한사항
- 입출력 예 1
- 입력 : "17"
- 출력 : 3
- 설명 : [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있음
- 입출력 예 2
- 입력 : "011"
- 출력 : 2
- 설명 : [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있음
Solution
function solution(numbers) {
let answer = new Set();
const numArr = numbers.split('');
function isPrime(n) {
if (n < 2) return false;
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) return false;
}
return true;
}
function getPermutation(arr, fixed) {
if (arr.length === 0) return;
for (let i = 0; i < arr.length; i++) {
const newFixed = fixed + arr[i];
const newNumber = parseInt(newFixed);
const copyArr = [...arr];
copyArr.splice(i, 1);
if (!answer.has(newNumber) && isPrime(newNumber)) {
answer.add(newNumber);
}
getPermutation(copyArr, newFixed);
}
}
getPermutation(numArr, '');
return answer.size;
}- 풀이 설명
- 중복을 제거하기 위해 Set 사용
- 소수 찾기 : 2부터 자신의 양의 제곱근 이하의 수까지 나누어 소수인지 판별
- 순열 계산
- 고정시킨 값과 배열의 나머지 요소들 중 선택하여 새로운 고정값을 만들어냄
- 새로운 고정값이 set에 없고, 소수라면 set에 추가함
