-
[LeetCode] 11. Container With Most Water Solution (C++)Algorithm/C++ 2020. 5. 31. 01:20
문제 원문 링크 : https://leetcode.com/problems/container-with-most-water/
얼핏 보면
https://www.acmicpc.net/problem/1725
문제와 비슷하다.
그래서 맨 처음에 아무 생각없이 위 문제와 같은 방법으로 접근했더니 역시나 Wrong Answer!
문제 제대로 읽자.일단 가장 먼저 떠오르는 방법인 Brute Force(완전 탐색)으로 접근해보자.
이것 역시나 정답은 아니었다.
이런
무지막지하게 긴input이 있기 때문이다.
모든 경우의 수를 다 탐색하지 않는 접근법이 있을까?
각 블럭에서 가장 크게 만들 수 있는 컨테이너는 해당 블럭을 기준으로,
1. 가장 멀리 떨어져있으면서(= 가로 길이가 가장 길면서) 2. 높이가 크거나 같은 블럭과 만들게 되는 컨테이너이다.
그렇다면 양 끝에서부터 시작해서 어떤 블럭보다 큰 블럭이 나오면 그 블럭을 이용해 곧장 넓이를 구하고,
찾은 후에는 하나씩 안쪽으로 범위를 좁혀가면서 다른 블럭에 대해서도 넓이를 구하고 그 중에 최대를 취하면 되지 않을까?
이 접근 방식은 O(n)으로, Brute Force의 O(n^2)보다 훨씬 빠른 알고리즘이다.
코드를 구현하면 아래와 같다.
Code
https://github.com/changyeon2/Algorithm/blob/master/leetcode/problem%2011/C%2B%2B/solution%201.cpp
'Algorithm > C++' 카테고리의 다른 글
[Programmers] 입국심사 Solution (C++) (1) 2021.01.31