[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파
START :
[3코1파] 2023.01.04~ (295일차)
[4코1파] 2023.01.13~ (287일차)
[4코3파] 2023.10.01 ~ (25일차)
Today :
2023.10.25 [295일차]
Leetcode Stack 문제
뭔가 기초도 잘 모르면서 중상급 문제를 자꾸 깔짝이고 있는 듯한 느낌이 들어서,
밑바닥 돌이 잘 놔져있는지 돌다리도 두드려보고 건너기 위하여
leetcode tree 문제 복습겸 Stack 문제 다시 풀기
+코딩 인터뷰 189가지 프로그래밍 문제와 해법 완전분석 책이랑 같이 보기
[1] 20. Valid Parentheses
https://leetcode.com/problems/valid-parentheses/description/
문제 설명
'(', ')', '{', '}', '[' 및 ']' 문자만 포함하는 문자열 s가 주어지면 입력 문자열이 유효한지 확인함
- 열린 괄호는 동일한 유형의 괄호로 닫혀야 함
- 열린 괄호는 올바른 순서로 닫혀야 합니다.
- 모든 닫는 괄호 왼편에는 동일한 여는 괄호가 있어야 함
문제 풀이 방법
class Solution:
def isValid(self, s: str) -> bool:
parDict = {')':'(', '}':'{', ']':'['}
stack = []
for c in s:
if not stack:
if c in parDict.values():
stack.append(c)
continue
else:
return False
if c in parDict.values():
stack.append(c)
else:
if stack[-1] == parDict[c]:
stack.pop()
else:
return False
return len(stack)==0
내 코드
좀 더 예쁘고 깔끔하게 다듬어 보자면
class Solution:
def isValid(self, s: str) -> bool:
stack = []
parDict = {')':'(', ']':'[', '}':'{'}
for c in s:
if c in parDict:
if stack and stack[-1]==parDict[c]:
stack.pop()
else:
return False
else:
stack.append(c)
return True if not stack else False
[2] 155. Min Stack
https://leetcode.com/problems/valid-parentheses/description/
문제 설명
stack class를 설계하는 알고리즘을 짜야한다.
getMin, top, pop, push 등의 메소드를 시간복잡도 O(1)에 해당하게 짜야한다.
getMin -> 스택 에서 가장 작은 원소 가져오기
top -> 스택의 최상단 원소 출력
pop -> 스택의 첫 원소 제거 (반환)
push -> 스택의 최상단에 데이터 쌓기
문제 풀이 방법
minStack 외에 나머지 메소드는 o(1) 로 가능한데,
stack에서 가장 작은 숫자를 가져오는 함수를 O(1) 로 실행하기 위한 고민이 필요하다.
minStack을 위해서 최소값을 저장해나가는 스택을 하나 더 만들어서,
값을 stack에 push 할때마다 최소값을 비교해서 최소값을 저장한 다음
minStack 메소드는 min 값을 저장하는 stack에서 가져온다.
나머지 메소드는 일반 stack에서 가져오면 됨!
시간복잡도 O(1), 공간복잡도 O(1) 로 실행된다.
내 코드
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
self.stack.append(val)
val = min(val, self.minStack[-1] if self.minStack else val)
self.minStack.append(val)
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
[3] 150. Evaluate Reverse Polish Notation
https://leetcode.com/problems/valid-parentheses/description/
문제 설명
Polish 표기법으로 산술 표현식을 나타내는 문자열 토큰 배열의 값을 나타내는 정수를 반환
- 유효한 연산자는 '+', '-', '*' 및 '/'
- 각 피연산자는 정수이거나 다른 표현식
- 두 정수 사이의 나눗셈은 항상 0을 향해 잘림
- 0으로 나누는 일은 없음
- 입력은 역방향 폴란드어 표기법으로 유효한 산술 표현식을 나타냄
- 답과 모든 중간 계산은 32비트 정수로 표현됨
문제 풀이 방법
문자열을 탐색하면서 연산자가 아닌 숫자들은 stack에 쌓고, 연산자가 등장하면
stack에 가장 위에 있는 데이터와 그 다음 아래에 있는 데이터 (가장 최신으로 들어온 숫자 2개)
들을 pop으로 가져와서 연산 한다.
+, *의 경우는 연산의 순서가 중요하지 않지만 -나 /의 경우에는 연산의 순서가 중요하므로,
pop을 두 번해서 각 변수에 담은 후에, 순서대로 연산한다.
내 코드
class Solution:
def evalRPN(self, tokens: list[str]) -> int:
stack = []
for token in tokens:
if token == '+':
stack.append(stack.pop()+ stack.pop())
elif token == '-':
a,b = stack.pop(), stack.pop()
stack.append(b-a)
elif token == '*':
stack.append(stack.pop()*stack.pop())
elif token == '/':
a,b = stack.pop(), stack.pop()
stack.append(int(b/a))
else:
stack.append(int(token))
return stack[0]
[4] 22. Generate Parentheses
문제 설명
n개의 소괄호 쌍을 이용해서 형식에 맞는 소괄호 조합을 return 함
문제 풀이 방법
stack을 이용해서 backtracking 전략으로 소괄호 조합을 만들어낸다.
손으로 트리로 내려가면서 그리는 거 까지는 성공했는데, 코드로 구현에 실패했음
나는 재귀함수 아직까지 잘 못다루겠음.. 재귀함수 이해는 되는데 막상 문제에서 코드로 구현하면 흘러가는 레파토리가 엉킨단 말여..
내 코드
lass Solution:
def generateParenthesis(self, n: int) -> list[str]:
stack = []
ans = []
def backtracking(openN, closedN):
if openN == closedN == n:
ans.append(''.join(stack))
return
if openN < n:
stack.append('(')
backtracking(openN+1, closedN)
stack.pop()
if closedN < openN:
stack.append(')')
backtracking(openN, closedN+1)
stack.pop()
backtracking(0,0)
return ans
[5] 739. Daily Temperatures
문제 설명
일일 온도 (정수) 담긴 배열 temperatures가 주어질 때,
인덱스가 i번째 날이라고 할 경우, i번째날 이후에 해당 인덱의 온도보다 따뜻한 날의 일수까지의 차이를 반환한다.
만약 i번째 날보다 따뜻한 기온이 없다면 0임.
문제 풀이 방법
처음에는 tempearature를 순회하면서 인덱스와 온도의 값을
처음부터 끝까지 순회하면서, 비교하고 크지않으면 다시 넣고, 다시 빼고 비교하고 넣고 하는 로직을 짰는데 잘 안됐다.
푸는 방법은 애초부터 온도의 배열의 길이와 같은 0으로 구성된 배열을 하나 더 만들고
temperature를 search 하면서 온도를 비교해나가면서 해당 인덱스의 차이를 새로운 배열에 넣는 것이다.
내 코드
class Solution:
def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
ans = [0] * len(temperatures)
stack = []
for i,t in enumerate(temperatures):
while stack and stack[-1][1] <t:
stackI, stackT = stack.pop()
ans[stackI] = i-stackI
stack.append([i,t])
return ans
[6] 853. Car Fleet
문제 설명
1차선 도로로 같은 목적지로 가는 자동차 n대가 있고, 목적지는 target으로 주어진다.
두 개의 정수 배열인 position과 speed가 주어지고 두 배열의 길이는 각 각 n이다.
position[i]는 i번째 자동차의 위치, speed[i]는 i번째 자동차의 속도(시간당 마일 단위)이다.
자동차는 앞서가는 차를 추월 할 수 없지만, 차를 따라잡아 같은 속도로 이동한다.
빠른 자동차는 더 느린 자동차의 속도에 맞춰서 속도를 늦추고, 두 자동차의 사이의 거리는 무시되며 동일 위치에 있다고 가정된다.
car fleet은 동일 위치, 동일한 속도로 주행하는 비어 있지 않은 자동차로,
자동차 한대도 car fleet이다.
한 자동차가 목적지 지점에서 car fleet으로 묶일 경우 하나의 car fleet으로 간주한다.
목적지에 도착하는 car fleet의 수를 반환하라.
문제 풀이 방법
사실 이거 예전에 한번 풀어보고 이해가 너무 안되서
하루 정도 걸렸던 문제인데, 한번에 못 풀었던 것만 기억나고 풀이가 기억 안나는 요지경 메모리
천천히 영상보면서 이해하고 코드로 구현된 로직을 보니까 이해완!
여기서 내가 이해하기 어려웠던 이유는 문제 이해를 하지 못해서이다.
여기서 중점으로 봐야하는 것은 차들이 동일 시간에 각자의 포지션에서 속도로 움직였을때, 동일한 위치에 같이 도착하게 된다면, 이건 하나의 car fleet이 되고, 도착점까지 계속 유지된다는 것이다.
왜냐하면 1차선 도로라 앞선 차를 추월하지 못하기 때문에, 뒤에있는 차가 속도가 아무리 빨라도 앞에 있는 차의 속도에 맞춰 가야 하기 때문이다.
각 자동차들의 도착시간은 (도착 위치 - 현재포지션) / 속도가 된다.
뒤에 있는 차들도 동일 위치에 위치하지 않더라도, 속도가 앞차보다 느리게 되면 하나의 car fleet이되고, 도착지 까지의 car fleet이 되는 자동차들은 pop 해버린 후,
마지막 stack에 남아있는 차를 return 해주면 된다! 휴!
내 코드
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pair = [[p,s] for p,s in zip(position, speed)]
stack = []
for p,s in sorted(pair)[::-1]:
stack.append((target-p)/s)
if len(stack) >=2 and stack[-1] <= stack[-2]:
stack.pop()
return len(stack)
[7] 20. Valid Parentheses
https://leetcode.com/problems/valid-parentheses/description/
문제 설명
각 막대의 너비가 1인 히스토그램의 막대 높이를 나타내는 정수 배열 height가 주어질 때, 해당 히스토그램에서 가장 큰 직사각형의 면적을 return 함
문제 풀이 방법
이것도 도대체 어떻게 풀어야 하는지..
brute force 로는 O(n^2) 이라 O(n)으로 최적화해서 푸는 방법은 각 배열의 인덱스 하나(높이)에서 구할 수 있는 최대의 면적을 maxArea로 업데이트 하는 것이다.
예를 들어 heights = [2,1,5,6,2,3] 이라고 했을때
첫 배열 원소 index = 0의 height =2 는
왼쪽 기준 바가 없고, 오른쪽 기준 바는 자신보다 낮은 높이를 가지기 때문에 오른쪽으로 이동해서 넓이를 구할 수 없다.
자기 자신의 위치에서 구할 수 있는 최대 넓이는 2이다.
다음으로 index =1의 height =1이고,
해당 인덱스에서 오른쪽으로 넘어가면 5라서 본인의 높이보다 크기때문에 옆으로 더 이동해볼 수 있다. 다음은 4,5,2,3 배열의 끝까지 넓이를 구할 수 있는데 가로 길이는 현재 인덱스 1, 끝 인덱스 6이므로 5 높이는 1로 최대 넓이는 5가 나오게 된다. 그리고 현재 자신의 바 면적인 1과 비교한다.
현재 면적보다는 옆으로 이동하면서 구한 넓이 5가 크므로 maxArea는 5가 된다.
이런식으로 하나의 막대를 움직여가면서 왼쪽,오른쪽 막대의 높이에 따라서 maxArea를 update 해간다.
얼추 이해는 됐는데 메인에서 start를 startI로 변환하고, stack에 넣을때 기존 h를 넣는 이유를 잘 모르겠네... ㅠ
내 코드
class Solution:
def largestRectangleArea(self, heights: list[int]) -> int:
maxArea = 0
stack = []
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] >h:
stackI, stackH = stack.pop()
maxArea = max(maxArea, (i-stackI)*stackH)
start = stackI
stack.append([start,h])
for i,h in stack:
maxArea = max(maxArea, (len(heights)-i)*h)
return maxArea
여담
스택 문제 왜 이렇게 정도가 없음
쉬우면 쉽고 어려우면 뒤지게 어렵네
