[코딩테스트 일지 - 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;
}
}코드 결과
