Algorithm - Exhausitive Search Problems

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 = 1189

Programmers 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	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에 추가함