[프로그래머스] #134 최소직사각형 (Swift)

https://programmers.co.kr/learn/courses/30/lessons/86491?language=swift 

코딩테스트 연습 - 최소직사각형

구현

명함의 가로와 세로 길이를 담은 [w,h] 배열이 명함의 갯수만큼 주어진다. (2차원배열, [[w,h]])

명함들을 적절히 90도 회전하여 (w,h)->(h,w) 모든 명함을 담을 수 있는 지갑의 최소한의 넓이구하는 문제

 

접근방법

처음에는 모든 명함들이 회전한경우,회전하지않은경우 의 지갑의 최소 넓이를 모두 구해야 하나 싶었다. (브루트포스)

하지만 명함의 갯수가 최대 10,000개 였고 위의 경우 2^n의 시간복잡도가 나와서 이건 아니구나 싶었다.

 

그러던중 w,h상관없이 가장 긴 길이를 알아내서 그 쪽(w or h)으로 나머지 명함들의 긴쪽을 모두 넘기면

최소 지갑의 넓이를 구할 수 있다는 것을 알게 됐다. (아 어제부터 자꾸 이말 쓰는데 좀 킹받는다)

여튼, 그렇게 나온 방법은 아래와 같다.

 

모든 명함을 순회하면서

가장 긴쪽 중에서도 가장 긴 값을 찾음, 그리고 동시에 가장 작은쪽 중에서도 가장 긴 값을 찾음

결과값으로 두 값을 곱한 값을 반환 = 최소 지갑의 넓이

 

처음에는 for-in 반복문 내에서 if 문을 사용했지만

이후 map과 max를 사용하여 코드를 개선함.

 

고차함수를 사용해서 긴코드가 줄어드는 과정을 보는게 재밌다 요즘. 역시 이래서 다들 함수형 플밍~ 함수형 플밍~ 하는구나 싶고~

마지막 코드가 한줄로 가장 간략하지만, 읽기 쉬운 클린코드의 측면에서는 두번째 솔루션함수가 가장 좋다.

 

소스코드

import Foundation

// 최초풀이
func solution(_ sizes:[[Int]]) -> Int {
    
    var maxOfMaxLength: Int = 0
    var maxOfMinLength: Int = 0
    
     for size in sizes {
         let maxLength = max(size[0], size[1])
         let minLength = min(size[0], size[1])
         if maxLength > maxOfMaxLength {
             maxOfMaxLength = maxLength
         }
         if minLength > maxOfMinLength {
             maxOfMinLength = minLength
         }
     }
    
    return maxOfMaxLength * maxOfMinLength
}

// 개선 풀이1
func solution2(_ sizes:[[Int]]) -> Int {
    
    let maxOfMaxLength: Int = sizes.map{ $0.max() ?? 0 }.max() ?? 0
    let maxOfMinLength: Int = sizes.map{ $0.min() ?? 0 }.max() ?? 0
    
    return maxOfMaxLength * maxOfMinLength
}

// 간략 코드
func solution3(_ sizes:[[Int]]) -> Int {
    return (sizes.map{ $0.max() ?? 0 }.max() ?? 0) * (sizes.map{ $0.min() ?? 0 }.max() ?? 0)
}