[알고리즘/프로그래머스/고득점Kit] 완전탐색(JS)

문제: 최소직사각형

---

https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=javascript 

프로그래머스

 

풀이

---

function solution(sizes) {
    // 가로, 세로 중 작은 값(세로)/큰 값(가로) 구분해서 각각의 최댓값을 곱한 값 
    sizes.map(size => size.sort((a, b) => a - b))
    let maxH = 0
    let maxW = 0
    
    for (let [h, w] of sizes) {
        maxH = Math.max(maxH, h)
        maxW = Math.max(maxW, w)
    }

    return maxH * maxW
}

 

---

 

문제: 모의고사

---

https://school.programmers.co.kr/learn/courses/30/lessons/42840?language=javascript 

프로그래머스

 

풀이

---

function solution(answers) {
    const s1 = [1, 2, 3, 4, 5]
    const s2 = [2, 1, 2, 3, 2, 4, 2, 5]
    const s3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    let scores = Array(4).fill(0)
    
    for (let i=0;i<answers.length;i++) {
        const a = answers[i]
        scores[1] += (a === s1[i%s1.length])
        scores[2] += (a === s2[i%s2.length])
        scores[3] += (a === s3[i%s3.length])
    }
    
    const maxS = Math.max(...scores)
    const bestS = [1, 2, 3].filter(s => scores[s] === maxS)
    return bestS
}

 

---

 

문제: 소수 찾기

---

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=javascript 

프로그래머스

 

풀이

---

function isPrime(num) {
    if (num <= 1) return false
    for (let i=2;i<=Math.sqrt(num);i++) {
        if (num % i === 0) return false
    }
    return true
}

function getPermutations(n) {
    const len = n.length
    const ch = Array(len).fill(0)
    const answer = []
    
    function DFS(str) {
        answer.push(+str)
        for (let i=0;i<len;i++) {
            if (ch[i] === 1) continue
            ch[i] = 1
            DFS(str + n[i])
            ch[i] = 0
        }
    }
    DFS('')
    return answer
}

function solution(numbers) {
    // numbers로 가능한 숫자 만들기(순열) -> 소수인 개수 구하기
    return Array.from(new Set(getPermutations(numbers))).filter(num => isPrime(num)).length
}

 

---

 

문제: 카펫

---

https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=javascript 

프로그래머스

 

풀이

---

function solution(brown, yellow) {
    // 약수 구해서 맞는지 확인
    const size = brown + yellow
   
    for (let i=1;i<=Math.sqrt(size);i++) {
        if (size % i === 0) {
            const w = size / i, h = i
            const ySize = (w - 2) * (h - 2) 
            if (size - ySize === brown) return [w, h]
        }
    }  
}

 

---

 

문제: 피로도

---

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=javascript 

프로그래머스

 

풀이

---

function solution(k, dungeons) {
    // DFS로 방문할 수 있는 가능한 순서로 돌면서 각 던전 방문할 때 감소한 피로도, cnt 넘겨주기 
    const N = dungeons.length
    const ch = Array(N).fill(0)
    let maxVal = Number.MIN_SAFE_INTEGER
    
    function DFS(hp, cnt) {
        maxVal = Math.max(maxVal, cnt) 
        
        for (let i=0;i<N;i++) {
            const [min, damage] = dungeons[i]
            
            if (ch[i] === 1 || hp < min) continue
            
            ch[i] = 1
            DFS(hp - damage, cnt + 1)
            ch[i] = 0
        }
    }
    
    DFS(k, 0)
    return maxVal
}

 

---

 

문제: 전력망을 둘로 나누기 

---

https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=javascript 

프로그래머스

 

풀이

---

function solution(n, wires) {
    // 먼저 양방향 그래프 만들고, 
    // wires 순서대로 각 요소 BFS 돌고 차이 구한다. 각 BFS 돌기 전 다른 요소는 체크해서 못 가게 하기 
    
    const graph = Array.from({ length: wires.length + 2 }, () => [])
    let minVal = Number.MAX_SAFE_INTEGER
    for (let [s, e] of wires) {
        graph[s].push(e)
        graph[e].push(s)
    }
    
    function BFS(cur, other) {
        // 연결된 개수 세서 리턴
        const q = []
        const ch = Array(wires.length + 2).fill(0)
        let cnt = 1
        
        ch[other] = 1
        ch[cur] = 1
        q.push(cur)
        
        while (q.length) {
            const x = q.shift()
            
            for (let i=0;i<graph[x].length;i++) {
                const nx = graph[x][i]
                if (ch[nx] === 1) continue
                
                ch[nx] = 1
                q.push(nx)
                cnt += 1
            }
        }
        return cnt
    }
    
    for (let [s, e] of wires) {
        const first = BFS(s, e)
        const second = BFS(e, s)
        minVal = Math.min(minVal, Math.abs(first - second))
    }
    return minVal
}

연결된 개수를 셀 때 처음에 cnt을 BFS 돌 때 큐에 같이 넣어서 셌다. 이건 최단 거리를 구할 때 쓰는 방법이고, 그냥 순회한 개수를 세려면 따로 정의 해서 큐에 넣을 때마다 하나씩 더해주면 된다. 잘 보고 세야지 ! 

 

---

 

문제: 모음사전

---

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=javascript 

프로그래머스

 

풀이

---

📚 나의 풀이

function solution(word) {
    // DFS 중단하고 값을 반환하려면 변수 cnt에 갱신하고 flag로 탈출할 수 있음
    // 중복을 허용하는 순열 
    const alphabets = ['A' ,'E', 'I', 'O', 'U']
    let answer = 0
    let cnt = 0
    
    function DFS(str) {
        if (str.length > 5) return // 5개까지만 탐색
        cnt += 1 // 몇 번째인지 세기
        if (str === word) {
            answer = cnt
            return
        }
        
        for (let alphabet of alphabets) {
            DFS(str + alphabet)
        }
    }
    
    DFS('')
    return answer - 1 // 빈 문자열 센 거 빼기
}

중복을 허용하는 순열을 만들어서 cnt을 증가시키면서 해당 단어를 찾으면 return하도록 했다. flag를 사용해 답을 찾으면 DFS를 중단시킨다.

 

if 문이 너무 정신 없는 거 같아서 다른 사람들 풀이를 살펴보니 아래처럼 length를 같이 넘기고, 객체에 답을 저장하는 방식도 있었다. 좀 더 자바스크립트스럽게 forEach도 썼다.. 배열 메서드를 잘 써야하는데 풀다보면 어느새 for문을 돌리고 있는 나를 발견할 수 있다. 신경써서 풀어야겠다..! 

function solution(word) {
    const alphabets = ['A' ,'E', 'I', 'O', 'U']
    let result = {}
    let cnt = 0
    
    function DFS(str, length) {
        if (length > 5) return // 5개까지만
        result[str] = cnt // 해당 단어 몇 번째인지
        cnt += 1
        alphabets.forEach(a => DFS(str + a, length + 1))
    }

    DFS('', 0)
    return result[word]
}