🖋️ 완전탐색 알고리즘 풀이

최소직사각형

• 명함은 가로/세로 회전 가능
• 작아서 들고 다니기 편한 지갑을 만들기
  
  
• 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes
• 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return

• 나의 코드

function solution(sizes) {
    // 회전이 가능하니
    // 가로, 세로 중 가장 긴 변끼리 모으고 짧은 변끼리 모으기
    // 후에 가장 긴 변과 짧은 것 중 가장 긴 변을 반환후 곱하기
    const [min, max] = sizes.reduce(([min, max], [a, b])
                                    => [Math.max(Math.min(a, b), min)
                                        , Math.max(Math.max(a, b), max)]
    , [0, 0])
    
    return min * max;
}

모의고사

• 삼인방은 모의고사에 수학 문제를 전부 찍기
• 가장 많은 문제를 맞힌 사람이 누구
  

1번 수포자가 찍는 방식: [1, 2, 3, 4, 5]
2번 수포자가 찍는 방식: [2, 1, 2, 3, 2, 4, 2, 5]
3번 수포자가 찍는 방식: [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]

• 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers
• 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return

• 나의 코드

function solution(answers) {
    // 1, 2, 3 수포자의 패턴 이차 배열
    const patterns = [
        [1,2,3,4,5],
        [2,1,2,3,2,4,2,5],
        [3,3,1,1,2,2,4,4,5,5]
    ]
    
    let max = 0;
  
    // 최댓값 갱신, 패턴에 따른 답안 비교 후 일치한 개수 매핑
    const result = patterns.map((p) => {
        const arr = answers.filter((v, i) => v === p[i % p.length]);
        max = Math.max(max, arr.length);
        return arr.length;
    });
    
    // 최댓값과 일치한 수포자 번호 배열 반환
    return result.map((v, i) => v === max ? i+1 : -1).filter((v) => v >= 0);
}

소수 찾기

• 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers
• 종이 조각으로 만들 수 있는 소수가 몇 개인지 return

• 나의 코드 (dfs 활용)

function solution(numbers) {
    // 조합을 구하고 소수인지 아닌지 filter 후 size 구하기
    return getCombi(numbers).filter(v => isPrime(v)).length;
}

const getCombi = (str) => {
    const answer = [];
    // 해당 idx 의 문자열을 사용했는지에 대한 배열
    const visited = Array.from({ length: str.length }, () => true);
    
    // 깊이우선탐색을 통한 완전 탐색
    const dfs = (cur) => {
        // 탐색한 숫자 추가, 문자열 숫자로 형변환
        answer.push(+cur);
        // 탐색한 숫자외의 숫자 조합 반복문
        for (let i = 0; i < str.length; i++) {
            if (visited[i]) {
                visited[i] = false;
                dfs(cur + str[i]);
                visited[i] = true;
            }
        }
    }
    dfs('');
    // 중복값을 없애기 위해 Set 후 배열 반환
    return [...new Set(answer)];
}

const isPrime = (n) => {
    // 1이하는 소수가 아님
    if (n <= 1) return false;
  
    // 제곱근 이하까지 반복문으로 소수인지 확인 가능
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            return false;
        }
    }
    return true;
}