99클럽 코테 스터디 9일차 TIL + 완전탐색(카펫)

오늘의 과제

프로그래머스 Lv.2에 정렬로 분류된 카펫입니다.

 

이번엔 기초라 생각되는 완전탐색으로 분류된 문제입니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

 

먼저 문제 요구사항 요약입니다.

 

가로의 길이가 세로 길이와 같거나 긴 사각형이 있습니다.

 

이 직사각형은 노란색과 갈색으로 채워져 있는데

먼저 노란색은 항상 가운데 있어야 하며,

갈색은 그 노란색을 둘러싸고 있어야 합니다.

 

최소 숫자인 노란색이 하나일 경우로 간단히 살펴보겠습니다.

 

입출력 예시 기준 두 번째이며

보시는 바와 같이 갈색 8개, 노란색 1개 입니다.

 

여기서 가로와 세로의 크기는 어떻게 구해야 할까요?

 

먼저 총 개수는 당연히 갈색 + 노란색입니다.

 

이 중 저희는 노란색 면적을 쉽게 구할 수 있습니다.

 

문제의 조건을 다시 보면 노란색은 중앙에 칠해져 있다. 라고 되어 있습니다.

 

가로의 길이가 세로 길이와 같거나 긴 사각형에서 중앙을 구하려면 갈색 부분만 도려내면 되겠죠?

 

 

빨간색으로 표시된 곳을 라인 따라서 지워내면 노란색 부분만 남게 됩니다.

 

즉, 사각형의 크기가 어떻게 되었든 저 빨간 화살표는 가장자리를 따라서 생기게 될 것이며

이에따라 노란색의 크기는 (행 - 2) * (열 - 2) 가 됩니다.

 

이제 문제의 분류답게 완전 탐색을 시작하면 되는데 문제의 최소 조건인 위 그림처럼

행이 세 개인 상태부터 시작하면 되고, 노란색의 개수가 위 공식과 같을 때 정답을 리턴하면 됩니다.

 

코드입니다.

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        // 주어진 색을 더하면 총 개수를 알 수 있다.
        int sum = brown + yellow;
        
        // 문제의 최소 조건인 3부터 시작한다.
        for (int i = 3; i <= sum; i++) {
            int row = i;
            int col = sum / row;
            
            // 공식이 성립되는 row, col을 찾았다.
            if ((row - 2) * (col - 2) == yellow) {
                answer[0] = row;
                answer[1] = col;
            }
        }
        return answer;
    }
}

 

배운 점

직접 그려보기 전까지 조금 헤맸던 문제입니다.

 

다행히 문제의 예시는 노란색이 하나가 아닌 두 개일때 가정한 그림이 제공되어

이후 연산도 유추할 수 있게 되었습니다.

 

물론 직접 그려보지 않고 계산식을 도출 해낼 수 있으면 좋겠지만

아직 숙달이 되지 않은 지금은 무작정 그리고, 무작정 적어가며 이해하는게 맞는 것 같습니다.

 

추가로 오늘 TIL을 작성하며 느낀 부분이 온전히 제 감상평이나 회고만을 적는게 아닌

혹시 볼 수도 있는 "누군가" 이 글을 보고 이해해야 한다고 생각하니 글을 적으면서도 조금 애매한 부분은

스스로 물음표를 던지며 조금 더 명확하게, 쉽게 설명하려고 노력하는 것 같습니다.

 

이를 통해 제 생각을 글로 적는 연습과 누군가에게 설명할 때의 연습 또한 되는 것 같습니다.

 

 

 

오늘의 한줄평

최고의 배움은 가르침이다.