항해99 알고리즘 3회차

스택

1. 링크드리스트의 반대 방향으로 해준다고 생각했다.

- 링크드리스트는 self.top.next = self.top

 

2. 자바는 배열로 처리했었는데 노드로 스택을 구현해서 스택은 자료구조 일 뿐인걸 다시 생각이 들었다. 꼭 배열이 아니여도 된다는 것

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        self.top = Node(data, self.top)

    def pop(self):
        if not self.top:
            return None

        node = self.top.data
        self.top = self.top.next
        return node

    def peek(self):
        if not self.top:
            return None

        return self.top.data


stack = Stack()

for i in range(3):
    stack.push(i)
    print(stack.peek())

stack.pop()
stack.pop()
print(stack.peek())

---

유효한 괄호 https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

 

처음에 테스트케이스에 "()[]{}"만 확인하면 끝나는 줄 알았다.

하지만 "{[]}" 구분을 해야 했었던 것

 

틀린 결과

    def isValid(self, s: str) -> bool:
        data = {
            ")" : "(",
            "]" : "[",
            "}" : "{",
        }

        for i in range(0, len(s)-1, 2):
            if s[i] != data.get(s[i+1], ""):
                return False

        return True

 

맞은 결과 - 스파르타 강의

 

강의를 바로 본 후 적용을 하였다.

not stack이 리스트에 값이 없을 때 확인하는 것 같다.

    def isValid(self, s: str) -> bool:

        data = {
            ")" : "(",
            "]" : "[",
            "}" : "{",
        }

        stack = []
        opener = "({["

        for i in s:
            if i in opener: # 열음
                stack.append(i)
            else: # 닫음
                if not stack:
                    return False

                if stack.pop() != data[i]:
                    return False
            
        return not stack

 

맞은 결과 - 파이썬 알고리즘 인터뷰

 

not stack에 대해 정확히 몰라서 헤맸던거 같다.

- 비어있으면 True를 반환

 

결과는 정확히 다 일치 할 경우 스택이 비어있으니 True를 반환

def isValid(self, s: str) -> bool:

    table = {
        ")" : "(",
        "]" : "[",
        "}" : "{"
    }

    stack = []

    if len(s) <= 1: 
        return False

    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

---

94. Binary Tree Inorder Traversal https://leetcode.com/problems/binary-tree-inorder-traversal

Binary Tree Inorder Traversal - LeetCode

 

스택 다른 문제를 풀려고 했는데 이진 트리를 중위 순회를 해야하는데 아예 짐작이 안가서 해답을 봤다

 

1. dfs 함수를 재귀함수로 깊이 탐색을 한다고 한다.

2. 1, 2, 3 순서로 나오는게 맞는데 stack.append의 위치를 left 탐색 후 넣어주기에 1,3,2가 나온다.

 

맞은 결과 - https://applepick.tistory.com/117

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

    stack = []
    def dfs(el):
        if el is not None:
            dfs(el.left)
            stack.append(el.val) 
            dfs(el.right)
    dfs(root)
    return stack

---

중복 문자 제거 https://leetcode.com/problems/remove-duplicate-letters

Remove Duplicate Letters - LeetCode

 

중복된 문자를 제거하고 stack에 담아서 정렬 후 결과를 냈는데

정렬 기준이 알파벳순이 아니라 사전식으로 정렬을 해야한다고 한다.

 

틀린 결과

def removeDuplicateLetters(self, s: str) -> str:
    stack = []

    for i in range(len(s)-1):
        flag = False

        for x in stack:
            if(s[i] == x):
                flag = True
                break

        if flag == False:
            stack.append(s[i])

    stack.sort()
    return ''.join(stack)

 

역순으로 앞으로 문자열을 보내주면서 저장을 했는데 틀렸다.

사전식으로 정렬하라는걸 내가 이해를 제대로 못한것같다.

그리고 애초에 문자열을 리스트로 전환해서 사용하면 돼서 스택이랑 상관이 없어져버렸다

 

틀린 결과

stack = []

for i in s:
    stack.append(i)

result = []
for i in reversed(stack):
    if i in result:
        continue

    result.insert(0, i)


return ''.join(result)

 

 

맞은 결과 - 파이썬 알고리즘 인터뷰

 

해답을 봐도 어려웠다.

사전적 정의를 이해하는데 시간이 많이 소모 됐는데, 정확히 알지 못한 느낌이다.

 

간단하게 생각하면 사전 단어 순서

- 중복된 값이 있으면 삭제 후 계속 뒤로 보낸다고 생각했다.

 

ebacabce는 acbe만 남는다

스택에 쌓일 때 아래 순서대로 된다.

값이 크거나 AND 뒤에 이미 있을 때 삭제

- e 

- b (e 삭제)

- a (b 삭제)

- a c

- a c b

- a c b e

def removeDuplicateLetters(self, s: str) -> str:
    stack, count = [], collections.Counter(s)
    for char in s:
        count[char] -= 1 # 개수를 빼준다.

        if char in stack: # stack에 이미 값이 있을 경우 넘김
            continue

        # 1. stack에 값이 있고
        # 2. 문자가 stack에 담긴 값보다 작고
        # 3. count의 개수 1개 이상이면
        while stack and char < stack[-1] and count[stack[-1]] > 0:
            stack.pop()

        stack.append(char)

    return ''.join(stack)

---

일일 온도 https://leetcode.com/problems/daily-temperatures

Daily Temperatures - LeetCode

문제 접근 🤔

• 반복문은 2개를 쓰는게 맞았다.
• 한개는 온도를 전부다 조회를 해야 했었고
  • 그 다음 반복문은 스택을 활용해서 돌려야했었다.

놓쳤던 부분 😅

• 접근 할 시에 반복문 2개를 사용하고
• 스택을 사용할려고 했는데 생각 한 대로 안됐다.
• 파이썬 알고리즘 인터뷰 분석
  • temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
  • enumerate로 인덱스와 값을 조회
  1. 스택에 인덱스를 담는다.
  2. 그 다음으로 가면 스택에 있는 인덱스의 값을 계속 비교해서 현재 값이 더 클 경우에는 스택에서 빼주고 3번 진행
  3. 현재 인덱스 - 스택에 담은 값으로 개수를 체크
     • 가능한 이유는 인덱스는 당연히 순차적으로 높아짐 스택에 담은 값은 전 인덱스기에 낮음

코드 😁

• 첫 번째 코드 - 파이썬 알고리즘 인터뷰

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        stack = []
        answer = [0] * len(temperatures)

        for i, cur in enumerate(temperatures):
            while stack and cur > temperatures[stack[-1]]:
                last = stack.pop()
                answer[last] = i - last
            stack.append(i)

        return answer

 

---

괄호 https://www.acmicpc.net/problem/9012

9012번: 괄호

문제 접근 🤔

• 강의를 보고 난 후 푸는거라 구상은 됐었다.
• “(” 이면 스택에 쌓고 “)”이면 스택에서 꺼내서 비교한다.

놓쳤던 부분 😅

•  예외처리가 헷갈렸었다.
  • “)”인데 스택에 없을경우 스택에 값을 넣고 끝낸다.
  • “(”이랑 “)”이랑 안맞으면 끝낸다.

코드 😁

• 첫 번째 코드

# 스택을 사용해서 푸는 문제
# 괄호가 제대로 닫혔는지 확인 하는 문제다.

import sys

N = int(sys.stdin.readline())

bracket_opener = {
    ")": "("
}

for _ in range(N):
    bracket = str(sys.stdin.readline())
    stack = []
    for s in bracket:

        if s == ")":
            if not stack:
                stack.append(s)
                break

            close = stack.pop()
            if bracket_opener[s] != close:
                break
            continue
        elif s == "(":
            stack.append(s)

    if stack:
        print("NO")
    else:
        print("YES")

---

스택 수열 https://www.acmicpc.net/problem/1874

1874번: 스택 수열

문제 접근 🤔

• 일단 스택을 1~N까지 넣어주면서 빼야한다. stack에 계속 쌓아주다가 입력한 숫자가 나오면 pop해준다.

놓쳤던 부분 😅

• 문제를 이해하는데 어려워서 블로그 해답의 설명을 읽고 시작했다.

코드 😁

• 첫 번째 코드 - 실패

import sys
from collections import deque

# 스택에 1~N까지 생긴다고 하면 해당 수를 pop해서 수열을 만들 수 있는지에 대한 문제

n = int(sys.stdin.readline())
m = deque([int(sys.stdin.readline()) for _ in range(n)])

stack = []
result = []

index = 1
while m:
    if index == m[0]:
        m.popleft()
        result.append("-")
        stack.pop()  # 1, 2, 3
        index -= 1

    elif index <= n:
        result.append("+")
        stack.append(index)
        index += 1

    elif index > n:
        index = 1

for i in result:
    print(i)

• 두 번째 코드 - 출처 티스토리

import sys

n = int(sys.stdin.readline())
stack = []
result = []
index = 1
for i in range(n):
    num = int(sys.stdin.readline())

    while index <= num:
        stack.append(index)
        result.append('+')
        index += 1

    if stack[-1] == num:
        stack.pop()
        result.append('-')

for i in result:
    print(i)