ZeroCho Blog

이번 시간부터는 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까지 풀었습니다. 중간에 가장 큰 정사각형 찾기랑, 땅따먹기같은 난이도 조절 실패 문제때문에 시간이 오래 걸렸네요.