[코딩테스트 풀이] 최소직사각형

소요시간: 1시간 20분

스트링 변환 문제는 자꾸 split("").map().join("")만 쓰게 되어서,
다른 형태의 문제가 필요하다고 생각했다.
그리고 발견한 최소직사각형

이 문제를 이해하는 것에는 어렵지는 않았지만 대체 어떻게 수식으로 풀어야할지 한참을 생각했다.
가장 큰 가로와 세로를 구하는데, 그 둘을 바꿔도 괜찮으면 큰 값을 구하지 말고 두번째 값으로 넣고....????????
손도 못대고 생각만 하다가 30분차에 힌트를 봤다.

"두개의 길이 모두 가로, 세로가 될 수 있다"

가로 세로에 갇히지 말고, 가로로 지정해버리면 되는 것!
(이 힌트 보고도 한참 걸렸다)

sort와 reduce를 이용한 풀이

최대처리시간 9.23ms

🤔 가로세로를 만들면 된다는 건 알겠는데, 그럼 대체 이걸 어떻게 비교하는가??

일차원 배열로 해결하려고 했던 것이 문제였다.
일차원 배열로는 풀 수 없는 문제... 이차원 배열로 접근해야했다.
reduce의 현재값을 [x,y]로 쪼개는 것까지 도출해내는 것이 오래 걸렸다.

function solution(sizes) {
    var answer = 0;
  	// 그럼 큰 값을 x로 작은값을 y로 정렬하고
    const sortedArr = sizes.map((v) => v.sort((a,b) => b-a))
    
    const {maxX, maxY} = sortedArr.reduce((acc, [x,y])=> {
      acc.maxX = Math.max(acc.maxX,x);
      acc.maxY = Math.max(acc.maxY,y);
      return acc;
},{maxX:0, maxY:0})
    // 가장 큰 x값 * 가장 큰 y값을 구하기
    return answer = maxX * maxY;
}

최대값을 찾으려면 Math.max()를 쓰려면 비교할 값이 필요한데,
어쩔 수 없이 빈 값을 하나 만들어야하나... 라고 생각했지만 reduce를 쓰면 해결되는 문제였다.
Math.max(acc.maxX,x)

테스트 중에 실행시간이 9.23ms 걸린 부분이 있었다. 왜일까?

foreach를 이용한 풀이

최대처리시간 6.67ms

다른사람의 풀이.
sort를 이용하지 않고 map으로 새로운 배열을 만들었다.
마찬가지로 큰 값이 왼쪽에 오도록 변경

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];
}

reduce와 Math.min, Math.max를 이용한 풀이

최대처리시간 6.02ms

다른사람의 풀이.
reduce의 총합도 h,v (가로세로인듯)로 구조분해해서 비교하는 방법.
내 풀이와 방향은 비슷하지만 이건 가독성이 별로 안좋은 것 같다.
시간은 세가지 방법 중에 제일 빠르게 나오긴 한다

function solution(sizes) {
    const [hor, ver] = sizes.reduce(([h, v], [a, b]) => [Math.max(h, Math.max(a, b)), Math.max(v, Math.min(a, b))], [0, 0])
    return hor * ver;
}