[코딩테스트 일지 - 99클럽] 3일차 - 카펫

코딩 테스트 준비 일지 3 일차

• 응시 사이트 : 프로그래머스

• 문제 : 카펫

• 난이도 : 중

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.

• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.

• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brown yellow return

10 2 [4, 3]
8 1 [3, 3]
24 24 [8, 6]

문제 풀이 접근

이 문제의 권장 풀이 시간은 1시간이었는데, 한번 풀이를 잘못 들어가서 1시간을 그냥 날리고 리셋해서 총 1시간 25분 정도 걸린것 같다.
방향을 잘못잡은 풀이는 최대한 이쁜 사각형만을 찾아서 감싸서 가로 세로 값 리턴해야지! 라는 안일한 생각으로 잘못 잡았다.
여기서 말한 최대한 이쁜 사각형이라는 것은 [18, 6] 이 주어졌을 때, [8, 3] 이 실제로 정답이나, 나는 가로 세로의 차이가 가장 적은 값인 [6, 4] 를 정답으로 판단해서 오류가 발생했던 문제였다.
직사각형이 정답이 될 수 있음을 무시하고, 정사각형에 최대한 가까운 것이 정답이라고 생각한 것에 대한 오류였다.

이렇게 문제를 풀면 풀리긴한다. 다만, 이 문제의 질문목록에 자주 올라오는 TC 4 6 7 나의 경우는 9 까지 패스할 수 없었다.
결론, 완벽한 정답이 아니다. ( 여기까지 했을때 1시간 지나버려서 리셋했다. )

다시 문제를 읽고 공식을 작성해보았고, 이런식을 세웠다.
1. Brown = (Yellow 의 열 * 2 ) + { 2 ( Yellow + 2) } 충족
2. Yellow = ( Yellow 가로 값 * 세로 값 ) 충족

이게 왜 이렇게 세워지냐면, 위의 [18, 6] 일 때, 6 이 Yellow 값인데, 3*2 인 Yellow 를 Brown이 감싸는 것에대해서 오류가 발생한다.

Yellow 값 또한, 약수로 분해했다. [1, 6] , [2, 3], [3, 2], [6, 1] 총 4개의 집합이 나온다.
여기서 중복되는 조합은 필요없고, 가로가 세로보다 길기 때문에 [1, 6] => [6, 1] , [2, 3] => [3, 2] 로 변경해서 필터링해서 패스했다.

결국 크게 보면 아래와 같이 3단계로 풀이가 정의된다.
1. Yellow 의 값을 약수 분해하라
2. Brown 공식과 Yellow 공식에 맞지 않으면 패스해라.
3. 최종적으로 나온 가로, 세로는 Yellow 의 가로 세로 값이기 때문에, 가로세로 두께인 2씩 더해서 출력하라. ( 세로의 경우 위 1 아래 1 , 가로의 경우 왼쪽 1 오른쪽 1 개씩 더있기 때문에, )

방향 잘못 잡은 코드 작성 ( C# )

using System;

public class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
            Tuple<int, int> pair = new Tuple<int, int>(0,0);
            int diffRecordValue = int.MaxValue;

            for(int i = 1; i < 2000000; ++i)
            {
                if (i > (yellow)) break;

                // yellow는 무조건 사각형이라는 가정, 정사각형, 직사각형 모두
                int balance = yellow % i;

                if (balance != 0) continue;
                // 사각형이 아니고 남으면 패스

                int div = yellow / i; // 나눠진 수

                int diffValue = Math.Abs(i - div);// 절댓값으로 차이를 구함. => 가장 가로세로 차이가 없는 이쁜 사각형을 구하기 위함.

                if (diffRecordValue < diffValue) continue;
                diffRecordValue = diffValue;

                if ( i > div )
                    pair = new Tuple<int, int>(i, div);
                else
                    pair = new Tuple<int, int>(div,i); 
                
                // 더 큰수가 가로
            }

            answer[0] = (pair.Item1) + 2;
            answer[1] = (pair.Item2) + 2;
        return answer;
    }
}

방향 잘못 잡은 결과

정답 작성 코드 ( C# )

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
              // 공식
   // Brown = ( Yellow열 *  2 ) + 2 ( Yellow + 2 )  성립

   // 분해된 수를 먼저 담아놓는다. 
   List<Tuple<int,int>> combinationList =new List<Tuple<int, int>>();

   for(int i = 1; i <= yellow; ++i)
   {
       // Yellow 수 까지 분해해서 약수를 담아놓는다.
       int balance = yellow % i;
       if (balance != 0) continue; // 나누어 떨어지지 않으면 담을 필요 없다. 

       int div = yellow / i;
       if (combinationList.Exists(rhs => rhs.Item1 == div && rhs.Item2 == i) == true) continue;
       if (combinationList.Exists(rhs => rhs.Item1 == i && rhs.Item2 == div) == true) continue;
       // 중복된 애들 필터링 

       if (div > i)
           combinationList.Add(new Tuple<int, int>(div, i));
       else
           combinationList.Add(new Tuple<int, int>(i,div));
   }

   // 이제 루프 돌면서 공식에 충족하는 애들을 추린다
   // Brown = ( Yellow + 2 ) + 2 ( Yellow + 2 )  성립
   // Yellow = div * i 가 Yellow 성립

   for (int i = 0; i < combinationList.Count; ++i)
   {
       var keyPair = combinationList[i];
       if (brown != (2* keyPair.Item1) + (2 * (keyPair.Item2 + 2))) continue;
       if (yellow != (keyPair.Item1 * keyPair.Item2)) continue;

       answer[0] = keyPair.Item1 + 2;
       answer[1] = keyPair.Item2 + 2;
       break;
   } 
        return answer;
    }
}

코드 결과