프로그래머스 문제 복습할 내용

소수찾기

    const prime = (number) => {
        if (number === 2) return true;
        if (number === 1 || number % 2 === 0) return false;
        for (let i = 3; i * i <= number; i += 2) {
            if (number % i === 0) {
                return false;
            }
        }
        return true;
    };

순열

    const permutation = (i, array, pick) => {
        if (i === pick) {
            if (prime(parseInt(array.slice(0, i).join("")))) {
                찾은소수.add(parseInt(array.slice(0, i).join("")));
            }
            return;
        }
        for (let j = i; j < array.length; j++) {
            [array[i], array[j]] = [array[j], array[i]];
            permutation(i + 1, numbersArray, pick);
            [array[i], array[j]] = [array[j], array[i]];
        }
    };

문자열끼리 합친 숫자 정렬

function solution(numbers) {
    const numbersToString = numbers.map((el) => el.toString());
    numbersToString.sort((a, b) => b + a - (a + b));
    return parseInt(numbersToString) === 0 ? "0" : numbersToString.join("");
}

객체가 존재하지 않으면 생성하고 존재하면 값 넣기

    const tCountObject = {};

    for (let i = 0; i < tangerine.length; i++) {
        tCountObject[tangerine[i]] = tCountObject[tangerine[i]] + 1 || 1;
    }

좌표 이동하기 BFS/큐/최단거리

    const command = [
        [0, -1],
        [0, 1],
        [-1, 0],
        [1, 0],
    ];

    let player = [[0, 0, 0]];

    while (player.length > 0) {
        const [x, y, moveCount] = player.shift();

        if (x === n - 1 && y === m - 1) {
            return moveCount + 1;
        }

        command.forEach((move) => {
            const xMove = x + move[0];
            const yMove = y + move[1];
            if (xMove >= 0 && yMove >= 0 && xMove < n && yMove < m) {
                if (maps[xMove][yMove] === 1) {
                    maps[xMove][yMove] = 0;
                    player.push([xMove, yMove, moveCount + 1]);
                }
            }
        });

 

DP 중복된 정답 존재, 반복

function solution(land) {
    for (let i = 1; i < land.length; i++) {
        land[i][0] += Math.max(land[i - 1][1], land[i - 1][2], land[i - 1][3]);
        land[i][1] += Math.max(land[i - 1][0], land[i - 1][2], land[i - 1][3]);
        land[i][2] += Math.max(land[i - 1][0], land[i - 1][1], land[i - 1][3]);
        land[i][3] += Math.max(land[i - 1][0], land[i - 1][1], land[i - 1][2]);
    }
    return Math.max(...land[land.length - 1]);
}

DFS 표시 남기기

function solution(k, d) {
    const N = d.length
    const visited = new Array(N).fill(0)
    let ans = 0

    function dfs(k, cnt){
        ans = Math.max(cnt, ans)

        for (let j = 0; j < N; j++){
            if (k >= d[j][0] && !visited[j]){
                visited[j] = 1
                dfs(k - d[j][1], cnt + 1)
                visited[j] = 0
            }
        }
    }

    dfs(k, 0)
    return ans;
}

재귀 DFS

  function solution(numbers, target) {
    let answer = 0;

    const depthFirstSearch = (depth, sum) => {
        if (depth === numbers.length) {
            if (sum === target) {
                answer++;
            }
            return;
        }
        depthFirstSearch(depth + 1, sum + numbers[depth]);
        depthFirstSearch(depth + 1, sum - numbers[depth]);
    };

    depthFirstSearch(0, 0);

    return answer;
}

다항식 계수의 합

=> [ 2, 1 ] // headgear 두 가지, eyewear 한 가지


아래의 조합을 구하는 식을 이용하여 답을 구합니다.

    for (let i = 0; i < countEachPart.length; i++) {
        result *= 1 + countEachPart[i];
    }

    return result - 1;
=> 5

// 즉 옷의 종류가 3가지고 각각의 옷의 개수가 a, b, c라면 (x+a)(x+b)(x+c) = x3 + (a+b+c)x2 + (ab+bc+ca)x + (abc)라는 식이 정립됩니다. 보이시죠? 총 조합의 개수가 계수에 다 포함되어 있습니다.

// 해당 식의 계수의 합을 구하려면 x=1을 대입해주면 됩니다. 그 후 맨 앞 x3 의 계수는 정답에 포함되지 않으므로 마지막에 1을 빼주는 겁니다.

// x=1을 대입한 식은 (1+a)(1+b)(1+c)가 되고 그 값에 1을 뺀 후 리턴해주면 정답이 나오는 이유가 그것입니다.

탐욕법

    let result = 0;
    const sortedPeopleArray = people.sort((a, b) => a - b);

    for (i = 0, j = people.length - 1; i <= j; j--) {
        if (sortedPeopleArray[i] + sortedPeopleArray[j] <= limit) {
            i++;
        }
        result++;
    }
    return result;
}

스택

function solution(s) {
    const stack = [];
    for (i = 0; i < s.length; i++) {
        if (stack[0] == undefined || stack[stack.length - 1] !== s[i]) {
            stack.push(s[i]);
        } else {
            stack.pop();
        }
    }
    return stack.length === 0 ? 1 : 0;
}

localeCompare 문자열끼리 비교 정렬

// string.sort((a, b) => a.localeCompare(b)); 내림차순 [a,b,c,A,B,C]
// string.sort((a, b) => -a.localeCompare(b)); 오름차순 [C,B,A,c,b,a]

해쉬테이블

function solution(participant, completion) {
    let hashed = []
    participant.forEach(entry => {
        hashed[entry] = hashed[entry] ? hashed[entry] + 1 : 1        
    })
    completion.forEach(entry => {
        hashed[entry] = hashed[entry] - 1
    })

    for (var key in hashed) {
        if (hashed[key] >= 1) return key
    }
}