[99클럽 코테 스터디] 16일차 TIL - 최소직사각형

Hoxy?·2024년 8월 6일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

16/42

오늘의 학습 키워드

</> 완전탐색

공부한 내용 본인의 언어로 정리하기

class Solution {
    public int solution(int[][] sizes) {
        //구해야 할 값인 가로와 세로의 최대길이 초기화
        int maxWidth = 0;
        int maxHeight = 0;
        
        //명항의 전체 사이즈를 순회하여 긴쪽을 가로로 짧은 쪽을 세로로 설정
        for(int[] card : sizes){
            int width = Math.max(card[0],card[1]);
            int height = Math.min(card[0],card[1]);
            
            //순회하면서 변경되는 값을 비교해 최대값 생성
            maxWidth = Math.max(maxWidth, width);
            maxHeight = Math.max(maxHeight, height);
        }
        //모든 명함이 들어갈 크기 완성
        return maxWidth * maxHeight;
    }
}

오늘의 회고

오늘은 어제 풀었던 문제를 리팩토링하다가 우연히 이해하게된 이차원배열을 완전탐색하여 생성가능한 최대 크기의 직사각형을 만들면 되는 문제로 이해했다.

우선 우리가 구해야 할 값은 명함의 가로와 세로의 최대크기를 구하면 된다. 그러기 위해서는 이차원배열을 이해해야한다.
예시를 보았을때

명함 번호	가로 길이	세로 길이
1	        60	        50
2	        30	        70

쉽게 말하면 int[][] sizes의 배열에서 int[0][0] sizes는 Index 0번 명함의 배열의 Index 0번은 60, Index 1번은 50이라는뜻이고 Index 1번 명함의 배열의 Index 0번은 30, Index 1번은 70이라는 뜻이다. 쉽게 말해 int[][] sizes에서 앞의 []는 명함번호 뒤의 [] 는 배열의 값이라는 말이다.

그래서 나는 명함 전체 사이즈를 반복문을 통해 순회하면서 Math.max와 Math.min을 사용해 큰 값을 가로 작은 값을 세로로 주었다.

for(int[] card : sizes){
	int width = Math.max(card[0],card[1]);
	int height = Math.min(card[0],card[1]);
            
	//순회하면서 변경되는 값을 비교해 최대값 생성
	maxWidth = Math.max(maxWidth, width);
	maxHeight = Math.max(maxHeight, height);
}

위의 코드를 보았을 때 배열의 값 2개를 비교해서 큰쪽을 width에 작은쪽을 height에 담는 것이 보일 것이다.
그리고 계속 입력 되는 값들을 새로 들어오는 값들과 비교해서 큰값을 계속 max값들에 들어가는 것도 볼 수 있다.

이제 최대의 길이를 두가지 다 구했으니 곱해주기만 하면 완성이 된다.

//모든 명함이 들어갈 크기 완성
return maxWidth * maxHeight;

오늘 문제는 순서와 과정만 잘 생각하면 쉽게 풀이되는 문제였던것 같다.

AI 코드리뷰

현재 코드의 장점

간결한 로직: 긴 쪽을 가로, 짧은 쪽을 세로로 설정하여 명함을 순회하며 최대 가로와 최대 세로를 계산하는 방식은 직관적이고 간결합니다.
효율성: 각 명함의 두 값을 비교하여 가로와 세로를 결정한 후 최대값을 갱신하는 방식으로 한 번의 순회로 문제를 해결합니다.
가독성: 변수명과 코드 구조가 명확하여 이해하기 쉽습니다.

현재 코드의 단점

제한된 범용성: 입력된 명함의 길이와 폭을 비교하여 가로와 세로를 설정하는 방식은 특정 경우에만 최적의 해를 보장하지는 않습니다. 모든 명함이 같은 방향으로 회전할 수 있는 경우를 가정하고 있습니다.
고정된 논리: 코드가 특정 문제에 고정되어 있어 다른 유형의 문제나 조건을 처리할 수 있는 유연성이 부족합니다.
시간 복잡도

이 코드는 모든 명함을 한 번씩 순회하면서 가로와 세로의 최대값을 갱신하므로 시간 복잡도는 𝑂(𝑛) 입니다. 여기서 𝑛 은 명함의 개수입니다.

개선된 코드 제안

class Solution {
    public int solution(int[][] sizes) {
        // 초기화
        int maxWidth = 0;
        int maxHeight = 0;

        // 모든 명함의 가능한 가로 세로를 확인
        for(int[] card : sizes) {
            int width1 = card[0];
            int height1 = card[1];
            int width2 = card[1];
            int height2 = card[0];

            // 각 경우를 비교하여 최대값 갱신
            maxWidth = Math.max(maxWidth, Math.max(width1, width2));
            maxHeight = Math.max(maxHeight, Math.max(height1, height2));
        }

        return maxWidth * maxHeight;
    }
}

개선된 버전의 장점: