stack(2)
-
Leetcode 42. Trapping Rain Water - Python
Leetcode 42 문제 보기 문제 이해하기 높이에 관한 정보가 주어질 때, 가둘 수 있는 빗물의 부피를 구하라. 예를 들어, height = [0,1,0,2,1,0,1,3,2,1,2,1] 일 때(위 그림 참조), 정답은 6이다. 아이디어 구상 가장 먼저 떠오른 생각은, 가장 높은 지점을 기준으로 좌우를 나누어 계산하면 될 것 같다라는 점이다. 다음처럼 생각해보자. 가장 높은 곳을 기준으로 좌측 영역을 우선 생각해보자. 첫 시작부터 포인터가 이동하면서 max값을 업데이트하며, max와 현재 지점의 높이의 차를 정답에 더해준다. 포인터는 전체에서 가장 높은 곳에 도달하면 멈추게 된다. 이렇게 되면 좌측 영역에서, 우측에는 분명한 '벽'(전체에서 가장 높은 지점)이 존재하므로 영역 내 높이 낮아지는 지점에..
2022.06.27 -
Leetcode 316. Remove Duplicate Letters - Python
Leetcode 316 문제 보기 문제 이해하기 소문자 알파벳으로 이루어진 문자열 s가 있다. (1 str: counter = collections.Counter(s) visited, stack = set(), [] for char in s: counter[char] -= 1 if char in visited: continue while stack and char 0: visited.remove(stack.pop()) stack.append(char) visited.add(char) return ''.join(stack) Leetcode 316. Remove Duplicate Letters https://leetcode.com/proble..
2022.05.07