[프로그래머스 알고리즘 고득점 Kit] 문제풀이 - 완전탐색

1. 최소직사각형

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

1-1. 내 풀이

먼저 정렬을 하여 긴 쪽과 짧은 쪽을 구분하였고, 각각 긴 쪽과 짧은 쪽의 최대값을 result 배열에 넣어 두 값을 곱해 결과를 반환했다.

function solution(sizes) {
    let result = [0, 0]
    sizes.map((item)=>{
        item.sort((a,b)=>b-a)
        if(result[0] < item[0]) result[0] = item[0]
        if(result[1] < item[1]) result[1] = item[1]
    })
    return result[0] * result[1];
}

 

2. 모의고사

https://school.programmers.co.kr/learn/courses/30/lessons/42840

프로그래머스

2-1. 내 풀이

반복분을 사용하여 각각 맞은 문제의 개수를 result 배열에 넣었다. 그리고 Math.max 를 사용하여 큰 값을 cnt 변수에 넣어 cnt 값과 각각 맞은 개수가 같으면 answer 배열에 해당 사람의 번호를 넣어 반환했다.

function solution(answers) {
    const one = [1,2,3,4,5];
    const two = [2,1,2,3,2,4,2,5];
    const three = [3,3,1,1,2,2,4,4,5,5];
    
    let result = [0,0,0];
    answers.map((item,index)=>{
        item === one[index % one.length] && result[0]++
        item === two[index % two.length] && result[1]++
        item === three[index % three.length] && result[2]++
    })
    
    let answer = [];
    const cnt = Math.max(...result);
    result.map((item,index)=>{
        item === cnt && answer.push(index+1);
    })
    
    return answer;
}

 

3. 소수

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

3-1. 내 풀이

중복된 수를 없애기 위해 Set 을 사용했고, 각 수를 방문했는지 확인하기 위해 isVisited 라는 배열을 만들었다.

 

다음으로 완전 탐색 함수를 통해 num 이 0 이상인 것만 set 에 넣었다.

그리고 반복문을 통해 방문하지 않은 수를 추가해 다시 완전 탐색 함수를 호출한다.

 

마지막으로 set 에 들어간 수들을 소수 판별하여 소수인 수의 길이만 반환했다.

function solution(numbers) {
    const result = new Set();
    const isVisited = new Array(numbers.length).fill(false);
    
    // 완전 탐색 함수
    const dfs = (num) => {
        if (num > 0) result.add(Number(num));

        for(let i=0; i<numbers.length; i++) {
            if(!isVisited[i]) {
                isVisited[i] = true;
                dfs(num + numbers[i]);
                isVisited[i] = false;
            }
        }
    }
    
    dfs('');
      
    // 소수판별 함수
    const isFrime = (num) => {
        if (num < 2) return false;
        for(j=2; j<=Math.sqrt(num); j++) {
            if (num % j === 0) return false;
        }
        return true;
    }
    
    return [...result].filter((item)=> isFrime(item)).length;
}

 

4. 카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

4-1. 내 풀이

brown 과 yellow 를 더한 값의 곱셈식(?) 의 배열이 답인걸 확인했고, 테두리는 값에서 각각 2을 곱하고 4를 뺀 수였다. 그래서 lineSum 이라는 변수를 만들어 brown 과 yellow 의 합에 나눠떨어지면서 그 값들을 더한 것이 lineSum 이면 반환하였다.

function solution(brown, yellow) {
    const lineSum = (brown + 4)/2;
    const sum = brown + yellow
    
    for(i=2; i<=Math.sqrt(sum); i++) {
        if (sum % i === 0) {
            const j = sum / i;
            if (j + i === lineSum) return [j,i]
        }
    }
}

 

5. 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

5-1. 내 풀이

각 수를 방문했는지 확인하기 위해 isVisited 라는 배열을 만들었다.

 

다음으로 완전 탐색 함수에서는 방문 횟수인 count 를 배열에 넣었고, 반복문을 통해 다음 방문할 곳이 현재 피로도보다 작고, 방문하지 않은 곳에서 다시 한 번 완전 탐색 함수를 호출하여 방문한다.

 

그래서 배열에 들어간 count 값들 중에서 가장 큰 값을 반환한다.

function solution(k, dungeons) {
    let answer = [];
    let isVisited = new Array(dungeons.length).fill(false);

    // 완전 탐색 함수
    const dfs = (k, count) => {
        
        answer.push(count);

        for(let i = 0; i<dungeons.length; i++) {
            if(k >= dungeons[i][0] && !isVisited[i]) {
                isVisited[i] = true;
                dfs(k-dungeons[i][1], count + 1);
                isVisited[i] = false; 
            }
        }
    }

    dfs(k, 0);
    
    return Math.max(...answer);
}

 

7. 모음 사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

7-1. 내 풀이

완전 탐색 함수를 이용하여 조합한 문자의 길이가 5가 넘으면 return 했고 result 객체에 각 문자를 Key에 index 값은 value 에 넣었다.

반복문을 돌려 현재 문자에 다음 문자을 붙이고 길이도 늘렸다.

 

그래서 result 에서 확인할 문자를 key 값으로 index 값인 value 를 반환한다. 

function solution(word) {
    const vowels = ["A","E","I","O","U"];
    const result = {};
    let index = 0;
    
    // 완전 탐색 함수
    const dfs = (w, len) => {
        if (len > 5) return;
        
        result[w] = index++;
        
        for (let i = 0; i < vowels.length; i++) {
            dfs(w + vowels[i], len + 1);
        }
    }
    
    dfs("", 0);
    
    return result[word];
}