[99클럽 코테 스터디_ DAY 16] 최소 직사각형

yewon·2024년 8월 7일
0

스터디

목록 보기
15/22
post-thumbnail
post-custom-banner

최소 직사각형

✏️오늘의 문제



💡나의 풀이


   public int solution(int[][] sizes) {
        int a =0; int b =0;
        
        // 1차웜 배열 0이 작은값 1인 큰값
       for(int i=0; i<sizes.length; i++){
           if(sizes[i][0] > sizes[i][1]){
               int temp = sizes[i][0];
               sizes[i][0] = sizes[i][1];
               sizes[i][1] = temp;
           }
       }
        for(int i=0; i<sizes.length; i++){
          if(sizes[i][0]>a){
              a = sizes[i][0];
          } if(sizes[i][1]> b){
              b = sizes[i][1];
          }

        }
        System.out.println(a+","+b);
        return a*b;
    }

코드 설명 단계별 분석

  1. 변수 초기화

    • int a = 0; : 최대 가로 길이를 저장할 변수입니다.
    • int b = 0; : 최대 세로 길이를 저장할 변수입니다.
  2. 각 카드 크기 정렬

    • 첫 번째 반복문을 통해 각 카드의 가로와 세로 길이를 비교하여, 항상 가로 길이가 세로 길이보다 작거나 같도록 정렬합니다.
  3. 최대 가로 및 세로 길이 찾기

    • 두 번째 반복문에서는 정렬된 배열을 순회하며, 최대 가로 길이(a)와 최대 세로 길이(b)를 찾습니다.
  4. 결과 출력 및 면적 반환:

    • 최종적으로 최대 가로 길이와 세로 길이를 출력하고, 두 값을 곱하여 직사각형의 면적을 반환합니다.

장점

  • 직관적인 로직: 코드가 간단하고 이해하기 쉬워, 주어진 문제를 해결하는 방법이 명확합니다.
  • 효율적인 시간 복잡도: 각 카드의 크기를 한 번씩만 반복하여 처리하므로 O(n) 시간 복잡도로 효율적입니다.
  • 유연성: 카드의 가로와 세로 길이를 정렬하여 모든 경우의 수를 고려할 수 있어, 다양한 입력에 대해 잘 작동합니다.

단점

  • 정렬 과정의 필요성: 첫 번째 반복문에서 카드 크기를 정렬하는 과정이 추가적인 연산을 요구합니다. 이로 인해 전체 시간 복잡도가 O(n)에서 O(n log n)으로 증가할 수 있습니다.
  • 메모리 사용: 입력으로 주어진 sizes 배열을 직접 수정하기 때문에 원본 데이터가 변형됩니다. 이로 인해 원본 데이터를 보존할 필요가 있는 경우 불편할 수 있습니다.
  • 입력 유효성 검사 부족: 입력 배열의 유효성 검사(예: 비어있는 배열)에 대한 처리가 없어, 잘못된 입력이 들어올 경우 예외가 발생할 수 있습니다.



💡 개선된 코드


public int solution(int[][] sizes) {
    int maxWidth = 0; // 최대 가로 길이
    int maxHeight = 0; // 최대 세로 길이

    // 최대 가로와 세로 길이 계산
    for (int i = 0; i < sizes.length; i++) {
        // 각 카드의 가로와 세로 길이를 비교하여 최대값 업데이트
        int width = Math.max(sizes[i][0], sizes[i][1]);
        int height = Math.min(sizes[i][0], sizes[i][1]);

        maxWidth = Math.max(maxWidth, width);
        maxHeight = Math.max(maxHeight, height);
    }

    // 최소 직사각형 면적 계산
    return maxWidth * maxHeight;
}

코드 설명

  1. 변수 초기화

    int maxWidth = 0; // 최대 가로 길이
    int maxHeight = 0; // 최대 세로 길이
    • maxWidth: 현재까지 발견된 카드 중 가장 큰 가로 길이를 저장하는 변수입니다. 초기값은 0입니다.
    • maxHeight: 현재까지 발견된 카드 중 가장 큰 세로 길이를 저장하는 변수입니다. 초기값은 0입니다.
  2. 최대 가로 및 세로 길이 계산

    for (int i = 0; i < sizes.length; i++) {
        int width = Math.max(sizes[i][0], sizes[i][1]);
        int height = Math.min(sizes[i][0], sizes[i][1]);
    • for 루프는 sizes 배열의 각 카드에 대해 반복합니다. 각 카드의 가로와 세로 길이를 가져와서 비교합니다.
    • Math.max(sizes[i][0], sizes[i][1]): 현재 카드의 가로와 세로 중 더 큰 값을 width에 저장합니다. 이 값은 해당 카드의 최대 가로 길이가 됩니다.
    • Math.min(sizes[i][0], sizes[i][1]): 현재 카드의 가로와 세로 중 더 작은 값을 height에 저장합니다. 이 값은 해당 카드의 최소 세로 길이가 됩니다.
  3. 최대 가로 및 세로 업데이트

    maxWidth = Math.max(maxWidth, width);
    maxHeight = Math.max(maxHeight, height);
    • maxWidth는 이전 최대 가로 길이와 현재 카드의 최대 가로 길이(width) 중 더 큰 값을 저장합니다. 이를 통해 모든 카드에서 최대 가로 길이를 찾습니다.
    • maxHeight도 마찬가지로 이전 최대 세로 길이와 현재 카드의 최소 세로 길이(height) 중 더 큰 값을 저장합니다. 이 과정을 통해 모든 카드에서 최대 세로 길이를 찾습니다.
  4. 면적 계산 및 반환

    return maxWidth * maxHeight;
    • 모든 카드의 최대 가로 길이와 최대 세로 길이를 곱하여 직사각형의 면적을 계산합니다.
    • 최종적으로 이 면적을 반환합니다.

예시 설명

예를 들어, sizes가 다음과 같다고 가정해 보겠습니다:

int[][] sizes = {
    {60, 50},
    {30, 70},
    {60, 30},
    {80, 40}
};
  • 첫 번째 카드: {60, 50} -> 최대 가로: 60, 최소 세로: 50
  • 두 번째 카드: {30, 70} -> 최대 가로: 70, 최소 세로: 30
  • 세 번째 카드: {60, 30} -> 최대 가로: 60, 최소 세로: 30
  • 네 번째 카드: {80, 40} -> 최대 가로: 80, 최소 세로: 40

이 값을 통해:

  • 최대 가로 길이(maxWidth): Math.max(60, 70) -> 70, Math.max(70, 60) -> 70, Math.max(70, 80) -> 80
  • 최대 세로 길이(maxHeight): Math.max(50, 30) -> 50, Math.max(50, 30) -> 50, Math.max(50, 40) -> 50

최종적으로 면적은 80 * 50 = 4000이 됩니다.

post-custom-banner

0개의 댓글