[Lv.2] 카펫 [프로그래머스_코딩테스트] [완전 탐색, 수학] [40분]

🔍 문제 요약

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

프로그래머스

노란색 격자가 카펫의 중앙에 들어가게 하면서 갈색 격자로 감싸는 카펫 모양을 만드려고 할 때 brown, yellow 격자의 개수가 주어졌을 때 가로 세로 격자 길이를 구하기

🧠 나의 접근 방식과 시행착오

대강 40분 정도 걸린 듯 하다. 처음에는 아래 주석처럼 yellow 개수를 구하는 식을 일단 변수 2개 (노랑 가로, 노랑 세로)를 써서 공식을 세우고, brown 개수도 찾는 식을 세운다. (노랑 가로 * 2 + 노랑 세로 * 2 + 4) 여기까진 시간을 허비하지 않았으나 공식대로 그냥 바로 답을 낼 수 있나 해서 두개의 방정식을 열심히 엮어서 풀어내려고 했으나 한 쪽변으로 가로 , 세로가 몰리지 않았어서.. 반복을 돌려서 가로를 하나씩 증가시켰을 때 새로의 길이를 구해서 반환하는 코드를 짰다. (반복문 안의 if문에 있는 예외처리가 그나마 신경을 좀 더 쓴 부분으로 yellow 격자의 개수를 가로로 나누었을 때 나누어 떨어지는 경우만 체크했다.)

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 카펫
    /// https://school.programmers.co.kr/learn/courses/30/lessons/42842
    /// </summary>
    public int[] solution(int brown, int yellow)
    {
        // 아래의 X가 노란색, O가 brown이 된다.
        // 9-sliced로 해서 일단 4각형의 각 모서리 4개의 Brown은 필수
        // 가로가 세로보다 길거나 같음
        // y_w : 노랑 가로
        // y_h : 노랑 세로
        // y_w * y_h = yellow
        // (y_w * 2) + (y_h * 2) + 4 = brown -> 노랑의 좌,우,상,하 + 4(모서리)
        
        /*
         
         OOO
         OXO
         OOO
         
         OOOO
         OXXO
         OOOO
         
         OOOOO
         OXXXO
         OOOOO
         
         OOOO
         OXXO
         OXXO
         OOOO
         
         OOOOOO
         OXXXXO
         OOOOOO
         
         OOOOO
         OXXXO
         OXXXO
         OOOOO
         
         */
        
        //  yWidth >= yHeight

        int[] answer = new int[2];
        
        // 가로 길이 1부터 yellow 개수까지 늘려감.
        for (int yWidth = 1; yWidth <= yellow; yWidth++)
        {
            int yHeight = yellow / yWidth;

            if (yellow % yWidth > 0 || yHeight > yWidth) continue;

            // 가능한 지 체크
            if ((yWidth * 2) + (yHeight * 2) + 4 == brown)
            {
                answer[0] = yWidth + 2;
                answer[1] = yHeight + 2;
            }
        }
        
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        int brown1 = 10;
        int yellow1 = 2;
        int brown2 = 8;
        int yellow2 = 1;
        int brown3 = 24;
        int yellow3 = 24;
        var res1 = sl.solution(brown1, yellow1);
        var res2 = sl.solution(brown2, yellow2);
        var res3 = sl.solution(brown3, yellow3);
        
        Console.WriteLine($"{res1[0]} {res1[1]}");
        Console.WriteLine($"{res2[0]} {res2[1]}");
        Console.WriteLine($"{res3[0]} {res3[1]}");
    }
}

✅ 풀이 코드

추가로 코드는 위에서 나온 케이스가 모든 케이스를 통과한 문제여서 따로 풀이 코드를 첨부하진 않았다. 여기서 개선할만한 피드백이 있을지 gpt에게 물어본 결과물. 확실히 피드백 1번을 보니 수식이 조금 많아지고 있긴 했던 듯 하다. brown 격자의 개수는 전체 격자 - 노랑 격자로 구할 수 있는 점을 활용하면 좀 더 명료한 느낌이긴 했을 것. (개선의 여지이나 필수는 아니다) 추가로 답이 여러개가 나올 수 있나? 싶긴 한데 아마도 한개만 나올 것으로 보여서 2번 피드백처럼 바로 답을 반환하는게 시간적인 측면에서도 효율적이고 맞을 듯 하다. (테스트 케이스가 정말 크거나 했었으면 문제가 생겼으려나 ..) (그래서 반복 한번만 돌리는 거라서 큰 상관은 없을 듯 하다 시간 복잡도면에서도 문제는 없을 듯 하니)

🔄 정리

중앙을 감싸는 격자 무늬의 개수가 주어졌을 때 식을 어느정도 빠르게 캐치를 한다면 문제는 쉽게 풀 수 있는 형태로 보인다. 방향을 잘못잡고 필자처럼 처음에 공식을 빠르게 찾았으나 그걸로 바로 답이 구해지려나 하면서 (반복을 돌리지 않고 바로 return 결과를 내는 방향) 시간을 허비하지 않고 반복을 돌려서 인자를 지정해서 찾아내는게 결국 맞다. 코딩 테스트란 결국 코딩 능력을 보는 것이니 수학적인 공식을 내는 것만이 답이 아니기에..