🔍 문제 요약
https://school.programmers.co.kr/learn/courses/30/lessons/86491
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
가로 세로 길이가 들어있는 Sizes라는 배열이 주어지고 해당 사이즈들을 모두 포함할 수 있는 최소의 사이즈의 너비를 구하는 문제. (가로 세로 전환 가능)
🧠 나의 접근 방식과 시행착오
대락 30분 정도 잡은 듯 하다. 문제에서 가로 세로를 전환할 수 있고 최소의 너비를 구하는 문제라 가로 최대, 세로 최대를 캐시하고 비교를 하면서 가로 세로를 전환했을 때에 포함이 되는 경우 캐시를 바꾸지 않고 넘어가고, 하나라로 넘치는 경우 전환했을 때와 전환하지 않았을 때 들어갈 수 있는 너비 중 더 작은 값으로 해서 계산하는 방식을 써봤다. 다만 이건 확신이 있게 푼 문제는 아니긴 함. 그렇지만 모든 테스트 케이스 통과한 문제긴 하다.
using System;
public class Solution
{
/// <summary>
/// 최소 직사각형
/// https://school.programmers.co.kr/learn/courses/30/lessons/86491
/// </summary>
public int solution(int[,] sizes)
{
// 가로, 세로 최대 길이 비교용
int rMax = 0;
int hMax = 0;
for (int i = 0; i < sizes.GetLength(0); i++)
{
int r = sizes[i, 0];
int h = sizes[i, 1];
// 1. 가로, 세로 둘 다 이전보다 작거나 같은 경우 상관 없이 다음 걸로 넘김
if (r <= rMax && h <= hMax)
{
continue;
}
// 2. 가로, 세로 둘 중 하나라도 이전보다 큰 경우 90도로 꺾어봄 (r,h 반전)
int rTemp = h;
int hTemp = r;
// 반전된 거가 이전거에 들어가는 경우 그냥 넘김
if (rTemp <= rMax && hTemp <= hMax)
{
continue;
}
int resR1 = Math.Max(r, rMax);
int resH1 = Math.Max(h, hMax);
int resR2 = Math.Max(rTemp, rMax);
int resH2 = Math.Max(hTemp, hMax);
int current1 = resR1 * resH1;
int current2 = resR2 * resH2;
if (current1 < current2)
{
rMax = resR1;
hMax = resH1;
}
else
{
rMax = resR2;
hMax = resH2;
}
}
int answer = rMax * hMax;
return answer;
}
}
/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
public static void Main(string[] args)
{
var sl = new Solution();
var size1 = new [,] { { 60, 50 }, { 30, 70 }, { 60, 30 }, { 80, 40 } };
var size2 = new [,] { { 10, 7 }, { 12, 3 }, { 8, 15 }, { 14, 7 }, {5, 15} };
var size3 = new [,] { { 14, 4 }, { 19, 6 }, { 6, 16 }, { 18, 7 }, { 7, 11} };
Console.WriteLine(sl.solution(size1));
Console.WriteLine(sl.solution(size2));
Console.WriteLine(sl.solution(size3));
}
}
✅ 풀이 코드
풀이의 핵심은 한쪽을 큰 값, 한 쪽은 작은 값으로 정렬하는 방식이다. 그렇게 하면 풀이 자체가 단순해진다. 한쪽으로 큰 값을 몰았기 때문에 뒤집어서 비교에 대한 풀이가 쉬워진다. 필자가 처음에 생각했던 것은 모든 경우를 다 비교해본다의 단순하게 생각했던 방식이라 풀이의 방식과 비교해보면 차이가 크게 보인다.
public int solution(int[,] sizes)
{
int maxWidth = 0;
int maxHeight = 0;
for (int i = 0; i < sizes.GetLength(0); i++)
{
int w = sizes[i, 0];
int h = sizes[i, 1];
// 가로/세로를 큰 값이 앞으로 오도록 정렬
int bigger = Math.Max(w, h);
int smaller = Math.Min(w, h);
// 전체 최대 가로/세로 갱신
maxWidth = Math.Max(maxWidth, bigger);
maxHeight = Math.Max(maxHeight, smaller);
}
return maxWidth * maxHeight;
}
🔄 정리
해당 문제처럼 모든 너비를 포함시킬 수 있는 최소값을 구하는 문제라면 한 쪽을 큰 값으로 고정한다라는 아이디어가 핵심일듯 하다. 일단 풀고 보는 습관에서 벗어나서 한 번 더 생각해보고 푸는 습관을 길러야 할 듯도 하다.
'Coding Test > Programmers' 카테고리의 다른 글
[Lv.1] 숫자 문자열과 영단어 [프로그래머스_코딩테스트] [문자열, 구현] [25분] (0) | 2025.06.02 |
---|---|
[Lv.1] 두 개 뽑아서 더하기 [프로그래머스_코딩테스트] [Set, 정렬] [25분] (0) | 2025.05.31 |
[Lv.1] K번째 수 [프로그래머스_코딩테스트] [정렬] [25분] (0) | 2025.05.30 |
[Lv.0] 개미 군단 [프로그래머스_코딩테스트] [수학, 구현] [15분] (0) | 2025.05.29 |
[Lv.1] 크기가 작은 부분 문자열 [프로그래머스_코딩테스트] [문자열, 슬라이딩 윈도우] [30분] (0) | 2025.05.29 |