복습하기3

중복문자제거, 일일온도, 괄호, 스택수열

03/14/2022

스택

유효한 괄호

열린괄호일 경우, 스택에 넣고, 닫힌괄호일경우 스택에 들어있는 괄호와 같은 종류의 것인지 확인하고 아니면 거짓을 반환하게한다.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        table = {
            ')': '(',
            '}': '{',
            ']': '[',
        }
        # 스택 이용 예외 처리 및 일치 여부 판별
        for char in s:
            if char not in table:
                stack.append(char)
            elif not stack or table[char] != stack.pop():
                return False
        return len(stack) == 0

중복문자제거

def removeDuplicateLetters(s: str) -> str:
    d = {char: index for index, char in enumerate(s)}
    final_s = []
    for index, char in enumerate(s):
        if char not in final_s:
            # final_s가 비어있지 X AND
            # 마지막의 요소보다 char의 우선순위가 높고 AND
            # 마지막의 요소는 뒤에서 한 번 더 나타난다는 보장 있는 경우
            # -> 마지막 요소 pop
            while final_s and final_s[-1] > char and d[final_s[-1]] > index:
                final_s.pop()
            final_s.append(char)
    return "".join(final_s)

여기서 내가 주의해야할 점은 continue 와 마지막 단어가 스택에서 어떻게 작동하는지에 대한 원리파악이였다.

일일온도

스택을 이용한 좀 소름돋는 풀이였다. 사실 어떻게 접근할지 감이 잡히지 않아서 바로 답안지를 봤는데, 이해하는데 2시간이 걸렸다. 보고나서 소름돋았다.. 이게 컴퓨터사이언스구나를 느꼈다...
다음온도가 낮아질경우 스택을 저장해서 다음온도가 높아질때까지 쌓아놓는다..그러고나서 높아질때부터 온도간의 차이를 이용해서 답을 리턴한다...소름이다..

def daily_temperatures(s):
  answer = [0] * len(T)
  stack = [] 
  for i, cur in enumerate(T):
    while stack and cur > T[stack[-1]]:
      last = stack.pop()
      answer[last] = i - last
    stack.append(i)
  return answer
T = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(T))

이걸 할때 잘 이해해야할것은 stack 과 answer의 원리이다. 디버깅으로 겨우 이해했다.

스택수열

문제이해하기 굉장히 까다로웠다...굉장히 까다로웠다...
각종 블로그 다 들어가서 이해했다...

https://www.acmicpc.net/problem/1874

count = 1
temp = True
stack = []
op = []
N = int(input())
for i in range(N):
    num = int(input())
    # num이하 숫자까지 스택에 넣기
    while count <= num:
        stack.append(count)
        op.append('+')
        count += 1
    # num이랑 스택 맨 위 숫자가 동일하다면 제거
    if stack[-1] == num:
        stack.pop()
        op.append('-')
    # 스택 수열을 만들 수 없으므로 NO
    else:
        temp = False
        break
#스택 수열을 만들수 있는지 여부에 따라 출력 
if temp == False:
    print("NO")
else:
    for i in op:
        print(i)

https://data-flower.tistory.com/98

이해하기 어렵다...스택자체가 나에게 너무 어렵다..
input 4
stack 123

input 3
stack 12

input = 6
stack = 125

input 8
stack 1257

input 7
stack 125

input 5
stack 12

input 2
stack 1

input 1
stack none

후...

괄호