다시푸는 코딩 테스트 준비 일지
응시 사이트 : 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분 가량은 합리적으로 풀이된 것 같다.
다시 푼 문제이므로, 이전 포스팅이 있다.
링크