Today I Learned

오늘 한일
1. LeetCode

• 11. Container With Most Water는 막대의 높이를 담은 int배열이 주어지고, 두개의 막대를 골라 가장 큰 넓이를 구하는 문제이다. 초기 작성한 코드는 다음과 같은 버블정렬과 유사한 방식으로 접근했고, Time Limit Exceeded가 발생했다.

	public int maxArea(int[] height) {
        int size=height.length;
        int max=-1;
        for(int width=size; width>0; width--){
            for(int first_x=0; first_x+width<size; first_x++){
                int result=calculate_area(first_x, first_x+width, height[first_x], height[first_x+width]);
                if(max<result)
                    max=result;
            }
        }
        return max;
    }

    private int calculate_area(int first_x, int second_x, int first_height, int second_height){
        return (second_x-first_x)*Math.min(first_height, second_height);
    }

보다 나은 방법이 생각나지 않는데, 수학적으로 접근을 해봐야하나 싶어 높이조건은 최대 10000, 배열크기는 최대 100000임을 확인해보았지만 확률적인 접근인듯하여 좀 더 생각을 해봐야 할 듯 하다.

TDD방식으로 넓이의 감소 경향성을 이용한 제약조건을 걸어보았는데, 마찬가지로 time limit exceeded가 발생하는 것으로 보아 큰 배열이 들어갔을 때 루프를 한번 돌며 발생하는 시간을 줄이는 방향으로 다시 시도를 해보면 좋을 것 같다.