본문 바로가기
개발/알고리즘

[LeetCode] 11. Container With Most Water (Javascript)

by 자몬다 2020. 7. 21.
728x90

https://leetcode.com/problems/container-with-most-water/submissions/

 

막대들이 주어지고, 가장 넓은 면적을 찾는 문제다.

이중포문과 완전탐색으로 풀었는데, 문제를 딱 봤을때 직관적으로 떠오르는 풀이방법이긴 하지만... 더 좋은 방법이 있지 않을까?

var maxArea = function(height) {
    // 위치 index, 높이 h인 object 배열을 만든다.
    const map = height.map((h, index)=> ({index, h}));
    
    let answer = 0;
    // 이중 포문...으로 모든 조합을 찾는다.
    for (let i = 0 ; i < map.length; i++) {
        for (let j = i + 1; j < map.length ; j++) {
            // 둘 중 높이가 낮은 쪽이 물의 높이가 된다.
            const min = Math.min(map[i].h, map[j].h);
            // index로 거리를 계산한다.
            const width = map[j].index - map[i].index;
            const area = min * width;
            // 계산한 넓이가 현재 answer보다 크면 재할당한다.
            if (area > answer ) answer = area;
        }
    }
    return answer;
};

 

원래는 소팅해서 뭔가 개선해볼 생각으로 객체로 만들었었는데, 완전탐색이면 그럴 필요가 없겠다.

var maxArea = function(height) {
    let answer = 0;
    // 이중 포문...으로 모든 조합을 찾는다.
    for (let i = 0 ; i < height.length; i++) {
        for (let j = i + 1; j < height.length ; j++) {
            // 둘 중 높이가 낮은 쪽이 물의 높이가 된다.
            const min = Math.min(height[i], height[j]);
            // index로 거리를 계산한다.
            const width = j - i;
            const area = min * width;
            // 계산한 넓이가 현재 answer보다 크면 재할당한다.
            if (area > answer ) answer = area;
        }
    }
    return answer;
};

댓글0