Today I learned
2022/01/18
회고록
1/18
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
9장 스택, 큐
1. 이론
- 데크(deque)
-
앞, 뒤 양쪽 방향에서 element 를 추가하거나 제거할 수 있다.
-
양 끝 element 접근하여 삽입 또는 제거 시, O(n) 이 소요되는 리스트에 반해, O(1) 로 접근 가능
from collections import deque
deq = deque()
deq.append(10)
deq.appendleft(0)
deq.pop()
deq.popleft()
deq.remove(10)
from collections import deque
deq = deque([1,2,3,4,5])
deq.rotate(1) # [5,1,2,3,4]
deq.rotate(-1) # [1,2,3,4,5]- 우선순위 큐
-> 대부분의 우선순위 큐 문제는 heapq 모듈 사용해서 풀이
- heapq 모듈 : 최소 힙(Min heap)지원
import heapq
# 일반적인 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와준다.
heap = []
# 힙에 원소 추가 O(logN)
heapq.heappush(heap, 1)
# 힙에서 원소 삭제 O(logN)
heapq.heappop(heap)
# 최소힙
# [1][2]..이후 요소들이 정렬되어 오름차순인 것은 X
# heappop 할 때, 이진 트리 재배치로 매번 새로운 최소값을 인덱스 0에 위치시키는 것
heap[0] #-최솟값 확인
# 리스트를 힙으로 변환
l = [1,2,3]
heapq.heapify(l)
- k 번째 최소값 / 최대값 찾기에 좋음
: heappop 할 때마다 최소값을 찾아서 pop 하고 그 다음 최소값을 [0] 위치에 갖다놓는다
: 따라서, heappop 을 k 번 호출하면서 최소값을 갱신하면 최종 최소값이 k 번째 최소값이 된다.
import heapq
def kth_smallest(nums, k):
heapq.heapify(nums)
for _ in range(k):
kth_min = heapq.heappop(nums)
return kth_min
nums = [8,6,5,4,25,13]
kth_smallest(nums, 4)2. 문제
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.
https://leetcode.com/problems/valid-parentheses/
3. MySol
def solution(input):
result = True
stack =[]
table = {
')':'(',
'}':'{',
']':'['
}
for char in input:
if char not in table:
stack.append(char)
elif not stack or table[char] != stack.pop():
return False
return len(stack) == 0
if __name__ == '__main__':
input = '()[]{}'
result = solution(input)
print('result : ' + str(result))
4. 배운 점
- 스택을 이용하여 풀기 좋은 괄호문제
- 스택을 이해하며 풀었다.
5. 총평
스택 훈련
https://github.com/jsw4215