[CodeKata] day-10

김민철·2020년 12월 13일
0
post-thumbnail

푼 날짜 : 2020.12.11

문제

인자인 height는 숫자로 이루어진 배열입니다.그래프로 생각한다면 y축의 값이고,높이 값을 갖고 있습니다.

아래의 그래프라면 height 배열은 [1, 8, 6, 2, 5, 4, 8, 3, 7] 입니다.

저 그래프에 물을 담는다고 생각하고, 물을 담을 수 있는 가장 넓은 면적의 값을 반환해주세요.

가정

배열의 길이는 2이상입니다.


내 풀이

(생각)
이중 for 문으로 돌려서 계산하면 구할 수 있는 넓이를 모두 구할 수 있다고 생각했습니다. 하지만 이중 for문이 가지는 big-O (N^2) 가 신경이 쓰였습니다. 여러 번 생각해봤지만 생각이 나지 않아 '이중 for 문으로 요소별로 구할 수 있는 넓이를 새로운 리스트에 추가하고, 그 리스트에서 최대값을 구하자'라고 결정하고 코드를 짰습니다.

이 풀이로 답을 맞출 수 있었습니다.


다른 사람 풀이

저는 이중 for문을 쓰지 않을때, 최대넓이를 어떻게 설정하고 값을 변경해 나갈지를 생각하지 못했습니다. 이 풀이를 보면 그래프로 생가했을 때, 양 끝에서 두 개의 포인트를 움직이며 넓이를 구하고 있습니다. 특히나 풀이에서 while 문 안의 if 조건이 인상 깊습니다.

저 방식으로 두 개의 포인트를 움직일 수 있다는 생각을 하지 못했습니다. 풀이가 직관적이면서 시간복잡도 또한 O(n) 으로 낮습니다.
구현해내고 싶었던 풀이를 보니 기분이 좋으면서 묘합니다.

0개의 댓글