코딩테스트 준비 - 카펫

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : Programmers

• 문제 : 카펫

• 사용언어 : C#

• 난이도 : 중

• 풀이시간 : 34m 44s

• 유형 : 약수, 수식설정, 완전탐색

문제 설명

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]

문제 풀이 접근

이 문제는, 노란색 박스를 기준으로 갈색 박스를 두르는 문제다.
고로, 노란색 박스의 가로 세로 쌍을 어떻게 찾아야될지가 메인인 문제다.
노란색 박스의 가로 세로 쌍을 구한 이후에, 갈색 박스의 숫자와 맞는지 체크해야한다.

총 갈색 박스 공식 : (노란색 박스 Y + 2) * 2 + (노란색 박스 Y * 2 )
1) 갈색 위, 아래 박스 면 공식 : ( 노란색 박스 Y + 2 ) * 2
2 )갈색 좌,우 면 공식 : (노란색 박스 Y * 2 )

이 문제의 플로우는,
1. 노란색 박스의 약수 쌍을 구한다. => 코드의 make 함수
2.약수 쌍을 반복하며, 해당 하는 루프의 값을 갈색 박스 공식에 넣어 brown 과 동일한지 찾는다.
3.동일한지 찾은 후, 노란박스의 가로 세로쌍의 합과 노란박스로 주어진 값이 동일한지 찾는다.
4.모두 맞다면 각 brown을 포함한 카펫의 면을 출력해야하기 때문에 각 면을 하나씩 더한 결과를 돌려줘야한다. 그렇기 때문에 각 가로 세로쌍에 +2 씩 더한 후 반환한다.

정답 작성 코드 (C#)

using System;
using System.Collections.Generic;

  public class Solution
    {
        public int[] solution(int brown, int yellow)
        {
            int[] answer = new int[] { };

            List<int> list = make(yellow);

            if (yellow == 1)
            {
                int horizon = list[0];
                int vertical = list[0];

                answer = new int[2] {horizon+2,vertical+2};
                return answer;
            }

            for (int i = 0; i < list.Count; ++i)
            {
                for (int j = 0; j < list.Count; ++j)
                {
                    int horizon = list[i] >= list[j] ? list[i] : list[j];
                    int vertical = list[i] >= list[j] ? list[j] : list[i];

                    if (brown == (((horizon + 2) * 2) + (vertical * 2)))
                    {
                        if (horizon * vertical != yellow)
                            continue;

                        answer = new int[2] { horizon+2, vertical +2};
                        return answer;
                    }
                }
            }

            return answer;
        }

        public List<int> make(int a)
        {
            // 약수 쌍을 구하는 함수
            List<int> list = new List<int>();

            for (int i = 1; i <= a; ++i)
            {
                int div = a % i;

                if (div == 0)
                    list.Add(i);
            }

            return list;
        }
    }

코드 결과

이전 카펫문제를 풀때는 시간을 재고 풀지는 않았지만, 난이도 대비 30분 가량은 합리적으로 풀이된 것 같다.

다시 푼 문제이므로, 이전 포스팅이 있다.
링크