[프로그래머스] 카펫

young_pallete·2021년 8월 1일
0

Algorithm

목록 보기
4/32

시작하며 🍭

현재 Brute Force 예제를 조금씩 풀고 있어요.
그냥 한 번 훑어보겠다는 알고리즘도, 어느 정도 예제들의 절반을 향해가고 있습니다 💪🏻

일단 이 문제는 쉬워요. 하지만 그 도착하기까지 과정에 있어서 아이디어를 떠올리기가 꽤나 낯설더라구요. 아직은 오랜만에 하는 알고리즘이 익숙치 않나 봅니다.

일단 저같이 모르는 분들을 위해, 알고리즘의 아이디어를 설계하는 과정을 고찰하면 어떨까 해서, 고민하다 씁니다 😋

풀이과정 📃

저는 처음에는 다음과 같은 생각을 했습니다.

이건 완전탐색하는 게 낫겠다. 그러면 그냥 1~5000까지 패턴만 파악해서, 대입하면 풀 수 있지 않을까?!

네, 지극히 정상적인 발상이라 생각합니다!
하지만 여기서 좀 더 생각해보면 다음과 같은 조건이 발생합니다.

노란색이 0이 아니라면, 반드시 height는 3이상이어야 하죠.
(width >= height이기 때문입니다.)

그렇다면 결국에는 뭔가 height의 limit만 정하면, 문제를 효율적으로 풀 수 있겠다는 생각이 떠오릅니다. 결국 height와 width의 조건만 충족하면, 답은 구할 수 있으니까요.

만약 width와 height가 있다면, 해당 width와 height가 정답일 경우는 어떤 경우일까요? 다음 조건을 충족해야 할 겁니다.

Brown의 개수는 (가로 + 세로) * 2이다.
Yellow의 개수는 (가로 - 2) * (세로 - 2)이다.

그러면 사실상, for loop를 통해 이를 처리하면, 끝나겠죠!
그 결과, 저는 다음과 같이 풀었어요.

코드 💻

/*
    1. brown을 통해 가로 + 세로를 구한다.
        * (brown + 4) / 2 = (가로+세로)
    2. for문을 통해 임의의 가로, 세로를 정한다.
    3. 가로 및 세로를 대입하여 노랑이 적합한지를 구한다.
        yellow: (가로 - 2) * (세로 - 2)
    4. 리턴
*/

const getHalfPerimeter = (brown) => (brown + 4) / 2;
const checkValid = (yellow, width, height) => ((width - 2) * (height - 2)) === yellow ? true : false
const solution = (brown, yellow) => {
    const halfPerimeter = getHalfPerimeter(brown);
    for (let height = 3; height < halfPerimeter; height += 1) {
        const width = halfPerimeter - height;
        if (checkValid(yellow, width, height)) return [width, height]
    }
    // 만약 답이 없을 경우
    return -1;
}

마치며

뭔가 요새, 저렇게 주석을 통해 제가 할 일을 정리하고,
이를 함수로 구현하면서 처리하니까, 좀 더 선언적으로 문제를 접근할 수 있더라구요.

이상, 다음 문제를 풀러...!

profile
People are scared of falling to the bottom but born from there. What they've lost is nth. 😉

0개의 댓글