내용이 안 보인다면 쿠키/캐시를 지우고 새로고침 하세요!
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌26 - Algorithm - 4달 전 등록 / 3달 전 수정

프로그래머스 문제 풀이 Level 2

1번~10번
조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

이번 시간부터는 Level 2입니다! 10개씩 풀고싶은데 설명이 길어질 것 같은 문제가 있으면 개수를 좀 줄이겠습니다. 모든 문제는 제가 직접 푼 풀이이며, 더 나은 풀이가 있다면 알려주세요~ 못 푼 문제는 끙끙대며 풀어볼테니 스포 금지! 

Level 2 1번~10번

124 나라의 숫자 

1,2,4만으로 숫자를 표현합니다. 변형된 3진법입니다. 1, 2, 4, 11, 12, 14, 21, 22, 24, 41, 42, 44, 111 이런 순으로 숫자가 커집니다.

규칙만 찾으면 쉽습니다(반대로 규칙을 못 찾으면 어렵습니다). 3 대신 4가 있는 게 좀 까다롭습니다. 규칙은 3으로 나눴을 때 나머지를 보시면 됩니다.

function solution(n) {
    return n ? solution((n - (n % 3 || 3)) / 3) + (n % 3 || 4): '';
}

재귀를 통해 한 자리씩 만들어 나가도록 하였습니다.

가장 큰 정사각형 찾기 

Level 2에 있을 문제가 아닙니다. 프로그래머스 오류인 것 같네요. 훨씬 더 어렵습니다. [[0,0,1,1],[1,0,1,1]]같은 배열이 주어지면 그 안에서 1로 구성된 가장 큰 정사각형을 찾는 문제입니다.

[
[0, 0, 1, 1],
[1, 0, 1, 1],
]
굵게 표시한 1 부분의 크기가 4(2X2)입니다.

정사각형 하나는 작은 정사각형 4개로 쪼갤 수 있다는 데서 아이디어를 얻었습니다(위의 2X2 정사각형은 1X1 정사각형 네 개로 쪼갤 수 있습니다).

[
[0, 1, 1, 1, 1],
[0, 1, 1, 1, 1],
[0, 1, 1, 1, 0]
]

이런 3X3 정사각형은 2X2 정사각형 네 개로 쪼갤 수 있습니다(좌상, 좌하, 우상, 우하)

아래 풀이는 재귀로 푼 문제입니다. 그런데 무슨 연유에서인지 틀렸다고 나오더라고요. 확실히 정사각형이 커지면 콜스택 초과가 발생할 수도 있을 것 같습니다.

const map = {};
function solution(board, x = 0, y = 0, l = Math.max(board.length, board[0].length))
{
    if (l === 1) {
        return (board && board[x] && board[x][y]) || 0;
    }
    if (x >= board.length || y >= board[0].length) {
       return 0;
    }
    if (map[x + ',' + y + ',' + l]) {
        return map[x + ',' + y + ',' + l];
    }
    const sol1 = solution(board, x, y, l - 1);
    const sol2 = solution(board, x + 1, y, l - 1);
    const sol3 = solution(board, x, y + 1, l - 1);
    const sol4 = solution(board, x + 1, y + 1, l - 1);
    let result = Math.max(sol1, sol2, sol3, sol4);
    if (sol1 === sol2 && sol2 === sol3 && sol3 === sol4) {
        result = (Math.sqrt(sol1) ? Math.sqrt(sol1) + 1 : 0) ** 2;    
    }
    map[x + ',' + y + ',' + l] = result;
    return result;
}

이번에는 다이나믹 프로그래밍 으로 푼 풀이입니다. 이것도 정사각형은 작은 정사각형 네 개의 합이라는 원리를 이용한 것입니다. 큰 정사각형이 되려면, 좌상, 좌하, 우상, 우하의 작은 정사각형이 존재해야 한다는 것으로 해석할 수도 있죠. 따라서 넷 다 존재하는 경우, 우하 정사각형 숫자를 1 올리는 것입니다. 아래처럼요.

[
[0, 1, 1, 1, 1],
[0, 1, 2, 2, 2],
[0, 1, 2, 3, 0]
]

코드로 구현하면 다음과 같습니다. 0, 0, 0, 0일때만 1로 안 올리게 조심하면 됩니다.

function solution(board) {
    board.forEach((r, i) => r.forEach((f, j) => {
        if (!board[i - 1] || !board[i - 1][j - 1] || !board[i - 1][j] || ! r[j - 1] || !f) return;
        board[i][j] = Math.min(board[i - 1][j - 1], board[i - 1][j], r[j - 1]) + 1;
    }));
    return Math.max(...board.map(r => Math.max(...r))) ** 2;
}

**가 제곱 연산자인 것은 아시죠?

올바른 괄호

괄호 (와 )가 올바르게 짝지어져 있으면 true를 리턴합니다. ()()와 (())()는 올바른 괄호고, )()(나 (()(는 올바르지 않습니다.

스택을 흉내내서 (면 넣고 )면 빼면 될 것 같습니다. 최종 개수가 0이면 모두 짝지어진 것이라 올바른 괄호입니다. 단 스택을 직접 구현할 필요는 없습니다.

function solution(s){
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        s[i] === '(' ? count++ : count--;
        if (count < 0) return false;
    }
    if (count !== 0) return false;
    return true;
}

함수 안에서는 리턴으로 반복문을 멈출 수 있다는 것도 알아두세요. 반복문 부분은 배열의 every나 some으로 구현하거나, 재귀를 쓸 수도 있을 것 같은데 귀찮아서 패스합니다.

다음 큰 숫자

n보다 크면서 이진수로 변환했을 때 n의 이진수와 1의 개수가 같은 숫자를 찾습니다. 78(1001110)의 다음 숫자는 83(1010011)입니다.

이진법 1의 개수를 세고, n에서부터 1씩 올리면서 이진법 1의 개수가 같은지 비교하면 됩니다.

function solution(n) {
    const bin = n.toString(2).match(/1/g).length;
    while (n++) {
        if (n.toString(2).match(/1/g).length === bin) return n;
    }
}

toString(2)로 이진법으로 바꿀 수 있습니다. match(/1/g).length는 1의 개수를 세는 코드입니다. while문으로 이진법 1의 개수가 같을 때까지 숫자를 올립니다. 함수 안에서는 리턴으로 반복문을 멈출 수 있다는 것도 알아두세요.

땅따먹기

Level 2에 있을 문제가 아닙니다. 프로그래머스 오류인 것 같네요. 훨씬 더 어렵습니다.

1 2 3 5
5 6 7 8
4 3 2 1

위와 같은 땅이 있다면 위에서부터 5, 7, 4를 밟으면 점수가 최대가 됩니다(5를 골랐으면 바로 아래 8은 고르지 못합니다)

알고리즘 문제는 크게 두 가지로 나눌 수 있는데요. 하나는 공식이나 규칙을 찾아서 쉽게 푸는 문제, 다른 하나는 모든 경우의 수를 구해서 푸는 문제. 이건 후자입니다. 아까 가장 큰 정사각형 찾기도 후자였습니다. 윗줄에서부터 한줄씩 내려와 누적 최대 점수를 구하면 쉽습니다(바로 아랫줄로 못 가는 규칙은 적용하셔야 합니다).

1 2 3 5
9 10 11 12
12 14 15 16

이런 식이 됩니다. 예를 들어 첫줄 5를 골랐다면 다음 줄까지의 누적 최대합은 12입니다(8을 못 고르므로 5 + 7) 그리고 12까지 왔다면 그 다음줄의 누적 최대합은 16(12 + 4)가 되고요. 이렇게 최대인 15를 골라내면 됩니다.

코드로 구현하면 다음과 같습니다. 저는 첫 줄을 0 0 0 0이라고 생각하고 진행했습니다.

function solution(land) {
    return Math.max(...land.reduce((a, c, i) => {
        return [
            c[0] + Math.max(a[1], a[2], a[3]),  
            c[1] + Math.max(a[0], a[2], a[3]),
            c[2] + Math.max(a[0], a[1], a[3]),
            c[3] + Math.max(a[0], a[1], a[2]),
        ];
    }, [0, 0, 0, 0]));
}

Math.max(...arr)처럼 배열을 spread하는 문법을 기억하세요. 

숫자의 표현 

자연수 n을 연속한 자연수의 합으로 표현하는 가짓수를 묻습니다. 예로 15는 1 + 2 + 3 + 4 + 5, 4 + 5 + 6, 7 + 8, 15까지 네 가지입니다.

이 문제는 황당하게도 홀수인 약수의 개수를 묻는 문제입니다. 왜 그렇냐고요? 수학적 감각입니다... 연속된 숫자의 개수에 주목해주세요. 5, 3, 2, 1개입니다. 2는 15랑 매핑하면 됩니다. 6의 경우는 1 + 2 + 3, 6 이렇게 두 가지로 나타낼 수 있는데, 개수를 세보면 3과 1입니다. 홀수인 약수의 개수랑 일치하죠? 다른 숫자들도 해보세요.

function solution(n) {
    return Array(n).fill().map((v, i) => i + 1).filter(v => (!(n % v) && v % 2) ).length;
}

최댓값과 최솟값 

문자열에서 최댓값과 최솟값을 찾으면 됩니다. "1 2 3 4"면 1과 4죠.

문자열을 배열로 만들어서 최댓값, 최솟값 찾는 메서드를 쓰면 되겠습니다.

function solution(s) {
    const o = s.split(' ').map(v => +v);
    return [Math.min(...o), Math.max(...o)].join(' ');
}

Math.min(...o)와 Math.max(...o)처럼 배열을 spread하는 문법을 기억하세요.

최솟값 만들기 

[1, 4, 2], [5, 4, 4]가 주어진다면 각 배열에서 두 수 씩 뽑아 곱한 후, 그것들은 더한 값이 최소가 되도록 하는 문제입니다. 1 * 5 + 4 * 4, + 2 * 4면 29가 최소가 됩니다.

당황스러울 수도 있지만, 간단합니다. 첫 번째 배열은 오름차순으로, 두 번째 배열은 내림차순으로 정렬한 후 곱하고 더해나가면 됩니다.

[1, 2, 4] * [5, 4, 4] 이렇게 하면 되는 것이죠.

function solution(A,B){
    const b = B.sort((p, c) => c - p);
    return A.sort((p, c) => p - c).map((v, i) => v * b[i]).reduce((a, c) => a + c, 0)
}

피보나치 수 

n번째 피보나치 수를 구합니다. 재귀적(탑다운)으로 할 수도 있고, 그냥 저처럼 바텀업 방식으로 할 수도 있습니다. 1234567은 이걸로 나눈 결괏값을 리턴하라고 해서 넣어준 것입니다.

function solution(n) {
    const arr = [0, 1];
    for (let i = 1; i <= n; i++) {
        arr.push((arr[i - 1] + arr[i]) % 1234567);
    }   
    return arr[n];
}

혹시나 재귀 코드가 궁금하시다면 아래처럼 하세요.

function fibonacci(num) { 
if(num < 2) return num;
return fibonacci(num-1) + fibonacci(num-2);
}

행렬의 곱셈 

[[1, 4], [3, 2], [4,1]]과 [[3,3],[3,3]]이 주어지면 [[15,15],[15,15],[15,15]]가 반환되면 됩니다. 행렬의 곱셈은 수학적인 지식이므로 여기서는 더 자세하게 설명하지 않습니다.

첫 행렬의 열의 개수와, 두 번째 행렬의 행의 개수가 일치해야 하는 성질이 있죠. 그러면 결과물 행렬은 첫 행렬의 행의 개수 X 두 번째 행렬의 열의 개수가 됩니다. 결과물 행렬의 모양을 생각해서 내용물을 만들면 됩니다.

function solution(arr1, arr2) {
    return Array(arr1.length).fill().map((r, i) => Array(arr2[0].length).fill().map((v, j) => arr1[i].reduce((a, c, k) => a + c * arr2[k][j], 0)))
}

JadenCase 문자열 만들기 

단어의 첫 문자가 대문자이고, 나머지는 소문자인 문자열로 바꿉니다. 3people unFollowed me는 3people Unfollowed Me가 됩니다.

단어별로 쪼개서 첫 글자만 대문자로, 나머지는 소문자로, 설명 그대로 바꿔주면 됩니다. 참 쉽죠?

function solution(s) {
    return s.split(' ').map(v => { 
        return v.split('').map((a, i) => i ? a.toLowerCase() : a.toUpperCase()).join('');
    }).join(' ');
}

split-apply-combine 3단 기법인 셈입니다.

N개의 최소공배수 

여러 숫자 배열의 최소공배수를 구합니다. [2, 6, 8, 14]면 168입니다.

두 수의 곱은 최소공배수와 최대공약수의 곱과 같다는 성질과, 최대공약수는 유클리드 호제법으로 구할 수 있다는 성질을 이용해서, 두 수씩 최소공배수를 구해나가면 됩니다.

function solution(arr) {
    return arr.reduce((a, c) => {
        function u(n, m) { return m % n ? u(m % n, n) : n; }
        return a * c / u(a, c);
    }, 1);
}

u 함수가 재귀적으로 최대공약수를 구하는 함수입니다.

이렇게 Level 2까지 풀었습니다. 중간에 가장 큰 정사각형 찾기랑, 땅따먹기같은 난이도 조절 실패 문제때문에 시간이 오래 걸렸네요.

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

아직 댓글이 없습니다.