알고리즘 CODEKATA 44 (최소 직사각형)

문제 설명

명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

명함 번호	가로 길이	세로 길이
1	60	50
2	30	70
3	60	30
4	80	40

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• sizes의 길이는 1 이상 10,000 이하입니다.
  • sizes의 원소는 [w, h] 형식입니다.
  • w는 명함의 가로 길이를 나타냅니다.
  • h는 명함의 세로 길이를 나타냅니다.
  • w와 h는 1 이상 1,000 이하인 자연수입니다.

---

내 풀이

최종코드

import kotlin.math.*

class Solution {
    fun solution(sizes: Array<IntArray>): Int {
        var answer: Int = 0
     
        var arrSize = sizes
        
        for(i in arrSize.indices){
            arrSize[i].sort()
        }
        
        var horMax = arrSize.maxOf{it[0]}
        var verMax = arrSize.maxOf{it[1]}        
        
        answer= horMax * verMax
        
        return answer
    }
}

풀이 과정

import kotlin.math.*

class Solution {
    fun solution(sizes: Array<IntArray>): Int {
        var answer: Int = 0
        
        //1. 각 명함들의 길이를 무조건 긴게 가로 자리에 오게 다시 배열
        var arrSize = sizes
        
        for(i in arrSize.indices){
            arrSize[i].sort()
        }
        
        //2. 가로 중에 젤 큰놈 세로중에 젤 큰놈 구하기
        
        var horMax = arrSize.filter{it[i][0].max()}.toInt()
        var verMax = arrSize.filter{it[i][1].max()}.toInt()
        
        
        //3. 대장놈 곱하기
        answer= horMax * verMax
        
        return answer
    }
}

일단 문법적으로 맞는지 틀린지는 모르겠고 대충 이런느낌이면 되겠다 하는 식으로 뼈대를 만들었다.

그래도 혹시나하면서 코드실행해봤는데 역시나 안됨~!

그래도 사실

1번부터 이거 sort로 정렬될까 여부 모르고 그냥 써본건데 일단 오류는 안나는 걸 보니 원하는대로 잘 정렬됐는지는 몰라도 뭐가 작동이 되긴하는거같음

오류는 2번에서 났는데

타입 미스매치랑, max()가 참조가 안되는 오류 같음

import kotlin.math.*

class Solution {
    fun solution(sizes: Array<IntArray>): Int {
        var answer: Int = 0
        
        //1. 각 명함들의 길이를 무조건 긴게 가로 자리에 오게 다시 배열
        var arrSize = sizes
        
        for(i in arrSize.indices){
            arrSize[i].sort()
        }
        
        //2. 가로 중에 젤 큰놈 세로중에 젤 큰놈 구하기
        
        var horMax = arrSize.maxOf{it[0]}
        var verMax = arrSize.maxOf{it[1]}        
        
        //3. 대장놈 곱하기
        answer= horMax * verMax
        
        return answer
    }
}

사실 1번이 작동은 되는데 내가 원하는대로 정렬이 됐는지 확인도 안하고 하고있긴 했는데 일단

오류를 안나게 고친다음에 확인하려고 생각했음

2번에서 최대값을 구하는 방법을 생각했는데..

그냥 냅다 max()를 붙이면 어떻게 되나도 해봤는데 unresolved reference: max 이런거 나옴;;

그래서 안그래도 든 거 없는 뇌 쥐어짜봐야 의미 없을 것같아서

구글링으로 이중배열에서 최댓값구하는 방법을 검색하다가 maxOf라는걸 발견함

사실 해당 블로그의 설명을 다 이해하진 못했는데 먼가 이거 쓰면 될거 같기도? 하고

선무당식 코딩으로 해봤는데

? 통과함 ㄱㅇㄷ 이왜됨? ~~아싸바룡

---

다른 사람 풀이

import kotlin.math.max
import kotlin.math.min

class Solution {
    fun solution(sizes: Array<IntArray>): Int {
        val widths = mutableListOf<Int>()
        val heights = mutableListOf<Int>()

        sizes.forEach {
            widths.add(max(it[0], it[1]))
            heights.add(min(it[0], it[1]))
        }

        return widths.max()!! * heights.max()!!
    }
}

오 이분은 가로세로연구소를 각각 리스트로 지정해주고

sizes를 돌면서 max min사용해서

가로 리스트에는 sizes의 가로세로 비교해서 큰애를 추가해주고

세로 리스트에는 둘중에 작은애를 추가하는 식으로 푸심

class Solution {
    fun solution(sizes: Array<IntArray>): Int
        = sizes.map{it.maxOrNull()!!}.maxOrNull()!!*sizes.map{it.minOrNull()!!}.maxOrNull()!!
}

한줄로 끝내버린 분도 있음ㅋㅋ

근데 너무 짧아서 바로 해석이안되어버림

대충 어떤 느낌인지알겠는데..

---