23.04.15. programmers 코딩테스트 문제 풀기[3]

이번문제는 공통 지갑 만들기. 간단해 보이지만 약간 꼬아져 있다.

점점 현실에서 발생할만한 문제가 나오니 더 재밌다.

 

예를들어 pdf를 cropping하는 기능을 만든다고 생각해보자. 여러 사이즈의 pdf가 있는데, 내용물이 다 들어오는 어떤 특정 크기를 찾아서 cropping을 실행하고 싶을 때, 유사한 계산이 필요할 수 있겠다.

 

이전 문제는 너무 자세히 적으니 시간이 많이 걸려서... 머리로 조금 더 생각하면서 써봐야겠다.

 

우선 입력 양식은

[ [ 60, 50 ], [ 30, 70 ], [ 60, 30 ], [ 80, 40 ] ] => 4000

 

이런 식. 생각해보자. 우선 [w, h]로 입력값이 주어져있다.

w들과 h의 max을 찾아 곱하면 1차 가장 작은 면적이 될 것.

그렇지만 가로세로를 바꿀 수 있다(=줄여서 switch로 하자)는 전제 조건을 생각해보면, 

switch했을 때, max(w)와 max(h)둘 중에서 min값을 가지는 배열의 w를 max(h)와 비교하고, h를 max(w)와 비교해서,

둘 다 작아지거나, 한쪽만이라도 작아지면 switch하도록 하고 max(h)와 max(w)를 update해주는 방법.

 

주어진 case와 극단적인 case를 생각해보자. 한 번만 바꾸면 끝나는지?

[ [ 60, 50 ],

  [ 30, 70 ],

  [ 60, 30 ],

  [ 80, 40 ] ]

여기는 max(w)는 80, max(h)는 70. 

w만 살펴보면 min(w)을 가지는 배열은 [30, 70]

w인 30 < max(h)=70

h인 70 < max(w)=80

win, win이라서 switch하면,

max(w)=80, max(h)=50으로 줄어든다.

 

한번 더 검토해봐야하는지 이대로 끝내도 되는지 보자.

switch된 다음은 아래와 같은데 바꿀 경우 모두 max값을 넘게 된다.

[ [ 60, 50 ],

  [ 70, 30 ],

  [ 60, 30 ],

  [ 80, 40 ] ]

즉 검토할 것은 min(w) < max(h)인게 있는지일까?

 

그러나, min(h) < max(w)를 처음부터 비교하면 

[ [ 60, 50 ],

  [ 30, 70 ],

  [ 60, 30 ],

  [ 80, 40 ] ]

min(h) = 30, max(w)=80 즉 min(h) < max(w) 이니 바꿀지 판단해보자.

[ 60, 30 ]의 h는 max(w)인 80보다 작다. 그리고 w는 max(h)인 70보다 작다. 그러니 좋은 변경이다. 바꾸자.

[ [ 60, 50 ],

  [ 30, 70 ],

  [ 30, 60 ],

  [ 80, 40 ] ]

아무 변경도 없는 셈. 생각을 잘못했다. 즉, max값이 바뀌는지를 확인해야 하는것.

 

다시 정리하면, 바꿀 것을 찾는 것은 w나 h 기준으로 하나를 잡고 검토해야 하나, 한번만 한다고 끝나는것은 아니라는 것.

이때 검토 조건은, 바꿨을 때 max(w)나 max(h)가 작아져야 한다는 조건.

 

검토 대상은 max 값이라고 봐야할까?

카드나 화투 정리할 때를 생각해보자.

대충 모은 다음, 튀어나온 것만 옆으로 돌려서 정리한다.

 

즉 중간결론은, w나 h 중 하나 기준에서 max값의 array만 잡고 돌려보면 된다는 것.

그리고 돌렸을 때 max(w)*max(h)가 이전 보다 커지면 지금의 면적값이 최적이라는 뜻.

 

맞을까?

 

이제 코드를 짜보자.

 

완전 틀렸다.

max값을 바꿨을 때 더 커질 수도 있는 것.

 

그래서 변수에 가장 작은 값을 저장하도록 하고, 최대값이 이미 되돌린 값인 경우에 while문을 빠져나오도록 해서 작은 값 저장되어있는 것을 반환하도록 했다.

function solution(sizes) {

    function findMax(sizes) {
        let max = {
            "w": 0,
            "h": 0,
            "wIdx": 0
        }
        for (i in sizes) {
            if (sizes[i][0] < max["w"]) {
                max["w"] = max["w"]
            } else {
                max["w"] = sizes[i][0]
                max["wIdx"] = i
            }

            if (sizes[i][1] < max["h"]) {
                max["h"] = max["h"]
            } else {
                max["h"] = sizes[i][1]
            }
        }
        return max
    }

    let max = findMax(sizes)
    let switched = new Array(sizes.length).fill(false)

    function switching(idx, sizes) {
        let temp = sizes[idx][0]
        sizes[idx][0] = sizes[idx][1]
        sizes[idx][1] = temp
        return sizes
    }
    let res = max['w'] * max['h']

    while (true) {
        res = max['w'] * max['h'] > res ? res : max['w'] * max['h']
        if (switched[max['wIdx']]) {break}
        sizes = switching(max['wIdx'], sizes)
        switched[max['wIdx']] = true
        max = findMax(sizes)
    }
    return res
}

생각보다 간단하게 정리가 안되서 코드가 엄청 길어졌는데, 풀고나서 다른사람의 풀이를 보니 역시 단순하게 해결될 수 있는 것이었다.

 

간한게 구현한 사람의 로직을 보니, 결국 화투패 정리하듯 하는게 맞긴 했고, 두 값을 비교해서 긴쪽이나 짧은쪽으로 정렬하고, 양쪽 중 가장 큰 값을 찾는 방식이다.

function solution(sizes) {
    const rotated = sizes.map(([w, h]) => w < h ? [h, w] : [w, h]);

    let maxSize = [0, 0];
    rotated.forEach(([w, h]) => {
        if (w > maxSize[0]) maxSize[0] = w;
        if (h > maxSize[1]) maxSize[1] = h;
    })
    return maxSize[0]*maxSize[1];
}

 

map으로 정렬하고, forEach로 최대값을 찾고 리턴. 

 

조금 더 최소한의 변경으로 문제를 풀까 싶어서 너무 복잡하게 생각했던 것 같다.