프로그래머스 - 폰켓몬, 최소직사각형

다리를 다쳐 꼼짝없이 집에만 있다 보니...

문득 회사에 다니기 전 풀었던 알고리즘 문제가 생각나 프로그래머스에 들어갔다.

(심심해서 알고리즘을 풀다니! 대학생 시절 나였으면 상상도 못 했을 텐데)

 

이전 풀이를 보니... 귀엽기도 하고, 답답하기도 하고. 하하.

그때 풀던 level 1 문제 중 안 푼 게 있어서, 재미 삼아 풀어보았다.

 

언어는 JS로!

 

폰켓몬

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

function solution(nums) {
    var answer = 0;
    const selectLimit = nums.length / 2

    const ponketmons = nums.reduce((prev, acc) => {
        if (Object.keys(prev).length >= selectLimit) {
            return prev
        }
        return prev[acc] ? prev : {...prev, [acc]:true}
    }, {})
    
    answer = Object.keys(ponketmons).length
    
    return answer;
}

별문제 없이 풀면 된다.

 

다만 위 논리에서는 매 reduce함수가 동작할 때마다, 가져갈 수 있는 폰켓몬 수를 초과했는지를 체크하는데...

작성하면서도 걱정했지만, n이 커짐에 따라 실행 시간 초과가 뜰 수도 있었을 것 같았다!

 

추후 다른 사람의 답변을 보니

function solution(nums) {
    var answer = 0;
    const selectLimit = nums.length / 2

    const ponketmons = nums.reduce((prev, acc) => {
        return prev[acc] ? prev : {...prev, [acc] : true}
    }, {})
    
    answer = Math.min(Object.keys(ponketmons).length, selectLimit)
    
    return answer;
}

아하... 사실 reduce 함수에서 해당 로직을 체크해 줄 필요가 없었다.

어차피 고유한 폰켓몬 종류가 최대 선택 종류 개수를 넘으면, 그만큼을 가져가면 되는 것이니!

(처음에는 넘었을 경우 break를 써 실행 시간을 단축하려 했는데, reduce나 forEach는 내부적으로 break를 지원하지 않음을 깜빡!

위 생각이 처음 자리를 잡다 보니, 매 reduce문마다 개수를 체크하는 로직이 들어가고 말았다)

 

function solution(nums) {
  const max = nums.length / 2;
  const arr = [...new Set(nums)];

  return arr.length > max ? max : arr.length
}

고유한 폰켓몬만 찾으면 되므로, Set으로 변환하는 것이 의미상 가장 맞았던 듯싶다.

 

최소직사각형

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

function solution(sizes) {
    var answer = 0;
    
    const sortedSizes = sizes.map((size) => size.sort((x, y) => x - y))

    const [maxWidth, maxHeight] = sortedSizes.reduce((prev, acc) => {
        const [width, height] = prev
        const [targetWidth, targetHeight] = acc
        
        const newWidth = targetWidth > width ? targetWidth : width
        const newHeight = targetHeight > height ? targetHeight : height
        
        return [newWidth, newHeight]
    }, [0, 0])
    
    answer = maxWidth * maxHeight
    return answer;
}

너비나 높이, 둘 중 하나를 기준으로 모든 size들을 정렬한 후, 

정렬된 size들을 돌며 가장 큰 너비와 높이를 구하면 되겠다고 생각! → 그대로 구현해 줬다.

(다른 풀이도 다 비슷한 맥락이었던 듯)