프로그래머스 #6

DFS/BFS - 네트워크

그래프 DFS문제를 떠올리며 해결하였음
풀이 방법을 알고있어서 그런가 레벨3라고 생각못했음

function aux(computers, rowIdx, isVisited){
    computers[rowIdx].map((el, colIdx) => {
        if(!isVisited[colIdx] && el === 1){
            isVisited[colIdx] = true;
            return aux(computers, colIdx, isVisited);
        }
    })
}

function solution(n, computers) {
    const isVisited = Array(n).fill(false);
    let count = 0;
    
    for(let i = 0 ; i < n ; i++){
        if(!isVisited[i]){
            isVisited[i] = true;
            count++
            aux(computers, i, isVisited);
        }
    }
    
    return count;
}

완전탐색 - 모의고사

쉬어가는 겸 완전탐색을 해보았음
다른 사람들의 풀이를 보니 더 줄일 수도 있는 방법들이 있음..
간단한 문제라 생각했는데 얼마나 간단히 푸냐가 중요했던듯?

function solution(answers) {
    const p1 = [1, 2, 3, 4, 5];
    const p2 = [2, 1, 2, 3, 2, 4, 2, 5];
    const p3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
    
    let idx1 = 0;
    let idx2 = 0;
    let idx3 = 0;
    
    const answerCount = [0,0,0];
    
    const isOverflow = (idx, arr) => {
        idx++;
        if(idx >= arr.length) idx = 0;
        
        return idx;        
    }
    
    for(let i = 0 ; i < answers.length ; i++){
        if(p1[idx1] === answers[i]) answerCount[0]++;
        if(p2[idx2] === answers[i]) answerCount[1]++;
        if(p3[idx3] === answers[i]) answerCount[2]++;
        
        idx1 = isOverflow(idx1, p1);
        idx2 = isOverflow(idx2, p2);
        idx3 = isOverflow(idx3, p3);   
    }
    
    let max = Math.max(...answerCount);
    
    return answerCount.map((el, idx)=>{
        if(el === max){
            return idx+1;
        }
    }).filter((el)=>{
        return !!el;
    })
}

완전탐색 - 소수 찾기

주어진 숫자의 모든 경우의 수를 소수인지 확인하여야 했음
DFS를 사용하여 풀었음

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

function DFS(num, numbers, idx, count, isVisited, isPicked){
    const N = numbers.length;
    
    if(idx > N) return count;
    
    isPicked[idx] = true;
    num = num + numbers[idx];
    num = Number(num);
    
    if(!isVisited[num]){
        isVisited[num] = true;
        if(isPrime(num)) count++;        
    }
    num = String(num);
    
    for(let i = 0; i < N; i++){
        if(!isPicked[i]){
            count = DFS(num, numbers, i, count, isVisited, [...isPicked]);
        }
    }
    
    return count;
}

function solution(numbers) {
    const N = numbers.length;
    const isVisited = new Array(Math.pow(10,N)).fill(false);
    const isPicked = new Array(N).fill(false);
    let count = 0;
    
    for(let i = 0 ; i < numbers.length ; i++){
        count += DFS('', numbers, i, 0, isVisited, [...isPicked]);
    }
    
    return count;
}