스택(Stack)은 LIFO(Last-In, First-Out) 구조를 가지며, 요소를 삽입(push)하거나 삭제(pop)할 수 있다.
그래서 스택 관련 30문항을 올려두고 두고두고 보려고 한다.

📌 1. 괄호 짝 맞추기

문제: 문자열이 주어졌을 때, 괄호가 제대로 맞춰져 있는지 확인하는 함수를 작성하세요. 문자열은 '(', ')', '{', '}', '[', ']' 의 여섯 종류의 문자로만 이루어져 있습니다.

input: "()[]{}"
output: True

input: "([)]"
output: False

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            stack.append(char)
    return not stack

📌 2. 수식 계산

문제: 문자열로 된 수식을 입력받아서 계산한 결과를 반환하는 함수를 작성하세요. 수식은 +, -, *, /, (, ) 연산자와 정수로만 이루어져 있습니다.

input: "3 + 2 * 5"
output: 13

input: "(2 + 3) * 4"
output: 20

def calculate(s: str) -> int:
    stack = []
    num = 0
    op = '+'
    for i in range(len(s)):
        if s[i].isdigit():
            num = num * 10 + int(s[i])
        if s[i] in '+-*/()' or i == len(s) - 1:
            if op == '+':
                stack.append(num)
            elif op == '-':
                stack.append(-num)
            elif op == '*':
                stack.append(stack.pop() * num)
            elif op == '/':
                stack.append(int(stack.pop() / num))
            num = 0
            op = s[i]
            if op == ')':
                tmp = 0
                while stack:
                    tmp += stack.pop()
                    if stack[-1] == '(':
                        stack.pop()
                        break
                stack.append(tmp)
    return sum(stack)

📌 3. 올바른 괄호 문자열 만들기

문제: 괄호 개수 n이 주어졌을 때, 올바른 괄호 문자열을 만드는 모든 경우의 수를 출력하는 함수를 작성하세요.

input: 3
output: ['((()))', '(()())', '(())()', '()(())', '()()()']

def generateParenthesis(n: int) -> List[str]:
    def backtrack(result, s, left, right):
        if len(s) == 2 * n:
            result.append(s)
            return
        if left < n:
            backtrack(result, s + '(', left + 1, right)

📌 4. 옥상 정원 꾸미기

문제: 옥상 정원은 일렬로 된 여러 건물들이 있을 때, 앞에 있는 건물이 뒤에 있는 건물보다 높을 때만 그 앞의 건물에서 옥상 정원을 볼 수 있습니다. 각 건물의 높이가 순서대로 주어졌을 때, 옥상 정원에서 볼 수 있는 건물의 수를 구하는 함수를 작성하세요.

input: [6, 9, 5, 7, 4]
output: 3

def visible_buildings(buildings: List[int]) -> int:
    stack = []
    count = 0
    for height in buildings:
        while stack and height >= stack[-1]:
            stack.pop()
        stack.append(height)
        count += 1 if len(stack) == 1 else 0
    return count

📌 5. 중위 표기식을 후위 표기식으로 변환하기

문제: 중위 표기식이 주어졌을 때, 후위 표기식으로 변환하는 함수를 작성하세요. 중위 표기식은 연산자가 피연산자 사이에 위치하는 표기법입니다. 후위 표기식은 연산자가 피연산자 뒤에 위치하는 표기법입니다.

input: "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
output: "3 4 2 * 1 5 - 2 3 ^ ^ / +"

def infix_to_postfix(s: str) -> str:
    stack = []
    priority = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    result = []
    for token in s.split():
        if token.isdigit():
            result.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                result.append(stack.pop())
            stack.pop()
        else:
            while stack and stack[-1] != '(' and priority[token] <= priority.get(stack[-1], 0):
                result.append(stack.pop())
            stack.append(token)
    while stack:
        result.append(stack.pop())
    return ' '.join(result)

📌 6. 올바른 괄호 문자열

문제: 괄호로만 이루어진 문자열 s가 주어졌을 때, s가 올바른 괄호 문자열인지 판별하는 함수를 작성하세요. 문자열 s는 '(', ')'로만 이루어져 있습니다.

input: "()()"
output: True

input: "(())()"
output: True

input: ")()("
output: False

def is_valid_parentheses(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            stack.append(char)
    return not stack

📌 7. 스택을 이용한 큐 구현

문제: 스택을 이용해 다음 연산을 지원하는 큐(Queue)를 구현하세요.

• push(x) : 요소 x를 큐에 삽입합니다.
• pop() : 큐의 첫 번째 요소를 삭제합니다.
• peek() : 큐의 첫 번째 요소를 가져옵니다.
• empty() : 큐가 비어있는지 여부를 반환합니다.

queue = MyQueue()
queue.push(1)
queue.push(2)
queue.peek()  # 1을 반환합니다.
queue.pop()   # 1을 삭제하고 2를 반환합니다.
queue.empty() # False를 반환합니다.

class MyQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, x: int) -> None:
        self.stack1.append(x)
        
    def pop(self) -> int:
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()
        
    def peek(self) -> int:
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]
    
    def empty(self) -> bool:
        return not self.stack1 and not self.stack2

📌 8. 최소값 스택

문제: 스택(Stack)을 구현하면서, 스택 내에서 최소값을 반환하는 함수를 구현하세요.

stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)
stack.getMin() # -3을 반환합니다.
stack.pop()
stack.top()    # 0을 반환합니다.
stack.getMin() # -2를 반환합니다.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

📌 9. 중복 문자 없는 가장 긴 부분 문자열

문제: 문자열 s가 주어졌을 때, 중복 문자가 없는 가장 긴 부분 문자열의 길이를 반환하는 함수를 작성하세요.

input: "abcabcbb"
output: 3

input: "bbbbb"
output: 1

input: "pwwkew"
output: 3

def length_of_longest_substring(s: str) -> int:
    start = max_length = 0
    used_char = {}
    for i, char in enumerate(s):
        if char in used_char and start <= used_char[char]:
            start = used_char[char] + 1
        else:
            max_length = max(max_length, i - start + 1)
        used_char[char] = i
    return max_length

📌 10. 유효한 괄호의 갯수

input: "()()"
output: 2

input: "(())()"
output: 3

input: ")()("
output: 1

def count_valid_parentheses(s: str) -> int:
    stack = []
    count = 0
    for char in s:
        if char == '(':
            stack.append(char)
        elif stack:
            stack.pop()
            count += 1
    return count

📌 11. 후위 표기식 계산

문제: 후위 표기식으로 된 문자열 s가 주어졌을 때, 이를 계산한 결과를 반환하는 함수를 작성하세요. 후위 표기식은 연산자가 피연산자 뒤에 위치하는 표기법입니다.

input: "3 4 2 * 1 5 - 2 ^ / +"
output: 2

def eval_postfix(s: str) -> int:
    stack = []
    for token in s.split():
        if token.isdigit():
            stack.append(int(token))
        else:
            num2 = stack.pop()
            num1 = stack.pop()
            if token == '+':
                stack.append(num1 + num2)
            elif token == '-':
                stack.append(num1 - num2)
            elif token == '*':
                stack.append(num1 * num2)
            elif token == '/':
                stack.append(int(num1 / num2))
            elif token == '^':
                stack.append(num1 ** num2)
    return stack[-1]

📌 12. 올바른 괄호 문자열 만들기

문제: 괄호 개수 n이 주어졌을 때, 올바른 괄호 문자열을 만드는 모든 경우의 수를 출력하는 함수를 작성하세요.

input: 3
output: ['((()))', '(()())', '(())()', '()(())', '()()()']

def generate_valid_parentheses(n: int) -> List[str]:
    def backtrack(result, s, left, right):
        if len(s) == 2 * n:
            result.append(s)
            return
        if left < n:
            backtrack(result, s + '(', left + 1, right)
        if right < left:
            backtrack(result, s + ')', left, right + 1)
    
    result = []
    backtrack(result, '', 0, 0)
    return result

📌 13. 큐를 이용한 스택 구현

문제: 큐(Queue)를 이용해 다음 연산을 지원하는 스택(Stack)을 구현하세요.

• push(x) : 요소 x를 스택에 삽입합니다.
• pop() : 스택의 첫 번째 요소를 삭제합니다.
• top() : 스택의 첫 번째 요소를 가져옵니다.
• empty() : 스택이 비어있는지 여부를 반환합니다.

stack = MyStack()
stack.push(1)
stack.push(2)
stack.top()    # 2를 반환합니다.
stack.pop()    # 2를 삭제하고 1을 반환합니다.
stack.empty()  # False를 반환합니다.

class MyStack:
    def __init__(self):
        self.queue1 = collections.deque()
        self.queue2 = collections.deque()

    def push(self, x: int) -> None:
        self.queue2.append(x)
        while self.queue1:
            self.queue2.append(self.queue1.popleft())
        self.queue1, self.queue2 = self.queue2, self.queue1

    def pop(self) -> int:
        return self.queue1.popleft()

    def top(self) -> int:
        return self.queue1[0]

    def empty(self) -> bool:
        return not self.queue1

📌 14. 큐를 이용한 스택 구현 II

문제: 큐(Queue)를 이용해 다음 연산을 지원하는 스택(Stack)을 구현하세요.

• push(x) : 요소 x를 스택에 삽입합니다.
• pop() : 스택의 첫 번째 요소를 삭제합니다.
• top() : 스택의 첫 번째 요소를 가져옵니다.
• empty() : 스택이 비어있는지 여부를 반환합니다.
  큐의 연산만을 이용해 스택을 구현해야 합니다.

stack = MyStack()
stack.push(1)
stack.push(2)
stack.top()    # 2를 반환합니다.
stack.pop()    # 2를 삭제하고 1을 반환합니다.
stack.empty()  # False를 반환합니다.

class MyStack:
    def __init__(self):
        self.queue = collections.deque()

    def push(self, x: int) -> None:
        self.queue.append(x)
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self) -> int:
        return self.queue.popleft()

    def top(self) -> int:
        return self.queue[0]

    def empty(self) -> bool:
        return not self.queue

📌 15. 이진 트리의 후위 순회

문제: 이진 트리의 루트 노드를 입력받아, 이진 트리를 후위 순회한 결과를 리스트로 반환하는 함수를 작성하세요. 이 문제에서 후위 순회는 왼쪽 자식 노드, 오른쪽 자식 노드, 자신 노드 순서로 방문합니다.

input: [1,null,2,3]
output: [3,2,1]

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorder_traversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack, result = [(root, False)], []
    while stack:
        node, visited = stack.pop()
        if visited:
            result.append(node.val)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return result

📌 16. 다음 큰 숫자

문제: 어떤 수 n이 주어졌을 때, n보다 크고 비트 중 1의 개수가 같은 수를 찾는 함수를 작성하세요. 단, 1 <= n <= 1,000,000 입니다.

input: 78
output: 83

def next_greater_number(n: int) -> int:
    bits = list(bin(n)[2:])
    i = len(bits) - 1
    while i > 0 and bits[i - 1] >= bits[i]:
        i -= 1
    if i == 0:
        return -1
    j = len(bits) - 1
    while bits[j] <= bits[i - 1]:
        j -= 1
    bits[i - 1], bits[j] = bits[j], bits[i - 1]
    bits[i:] = reversed(bits[i:])
    result = int(''.join(bits), 2)
    return result if result <= 1_000_000 else -1

📌 17. 가장 긴 증가하는 부분 수열

문제: 정수 배열 nums가 주어졌을 때, nums의 가장 긴 증가하는 부분 수열을 구하는 함수를 작성하세요.

input: [10,9,2,5,3,7,101,18]
output: 4

def longest_increasing_subsequence(nums: List[int]) -> int:
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

📌 18. 중위 표기식을 후위 표기식으로 변환

문제: 중위 표기식으로 된 문자열 s가 주어졌을 때, 이를 후위 표기식으로 변환하는 함수를 작성하세요. 중위 표기식은 연산자가 피연산자 사이에 위치하는 표기법입니다.

input: "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
output: "3 4 2 * 1 5 - 2 3 ^ ^ / +"

def infix_to_postfix(s: str) -> str:
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack, postfix = [], []
    for token in s.split():
        if token.isdigit():
            postfix.append(token)
        elif token in precedence:
            while stack and stack[-1] != '(' and precedence[token] <= precedence[stack[-1]]:
                postfix.append(stack.pop())
            stack.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                postfix.append(stack.pop())
            stack.pop()
    while stack:
        postfix.append(stack.pop())
    return ' '.join(postfix)

📌 19. 미로 탐색

문제: 2차원 그리드로 표현되는 미로가 주어졌을 때, 시작 지점부터 도착 지점까지의 최단 경로의 길이를 구하는 함수를 작성하세요. 각 칸은 벽이 있을 수도, 없을 수도 있습니다. 벽은 1로, 빈 칸은 0으로 표현됩니다. 시작 지점은 (0, 0)이고 도착 지점은 (N-1, M-1)입니다.

input: [[0,1,0,0,0], [0,1,0,1,0], [0,1,0,1,0], [0,0,0,1,0], [0,1,0,0,0]]
output: 10

from typing import List

def shortest_path(maze: List[List[int]]) -> int:
    m, n = len(maze), len(maze[0])
    start, dest = (0, 0), (m - 1, n - 1)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = [(start, 0)]
    visited = set([start])
    while queue:
        (i, j), steps = queue.pop(0)
        if (i, j) == dest:
            return steps
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and maze[ni][nj] == 0 and (ni, nj) not in visited:
                visited.add((ni, nj))
                queue.append(((ni, nj), steps + 1))
    return -1

📌 20. 괄호

문제: 주어진 문자열 s가 유효한 괄호 문자열인지 판별하는 함수를 작성하세요. 유효한 괄호 문자열이란 다음과 같습니다:

• 여는 괄호는 같은 타입의 여는 괄호로 닫혀야 합니다.
• 여는 괄호는 올바른 순서로 닫혀야 합니다.

input: "()[]{}"
output: True

def is_valid_parentheses(s: str) -> bool:
    stack = []
    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or abs(ord(stack[-1]) - ord(char)) > 2:
                return False
            stack.pop()
    return not stack

📌 21. 올바른 괄호의 갯수

문제: 주어진 숫자 n에 대해, n쌍의 괄호로 만들 수 있는 모든 "올바른 괄호 문자열"의 갯수를 반환하는 함수를 작성하세요.

input: 3
output: 5

def generate_parentheses(n: int) -> int:
    def backtrack(open_count, close_count):
        if open_count == close_count == n:
            return 1
        if close_count > open_count or open_count > n or close_count > n:
            return 0
        return backtrack(open_count + 1, close_count) + backtrack(open_count, close_count + 1)
    
    return backtrack(0, 0)

📌 22. 24 게임

문제: 4개의 숫자 카드와 더하기(+), 빼기(-), 곱하기(*), 나누기(/) 연산자를 사용해서 24를 만들 수 있는지 판별하는 함수를 작성하세요. 숫자 카드는 한 번씩만 사용할 수 있으며, 분수를 나타낼 때 괄호를 사용할 수 있습니다.

input: [4, 1, 8, 7]
output: True

def judge_point_24(nums: List[int]) -> bool:
    def dfs(nums: List[float]) -> bool:
        if len(nums) == 1:
            return math.isclose(nums[0], 24, rel_tol=1e-9)
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i != j:
                    next_nums = [nums[k] for k in range(len(nums)) if i != k != j]
                    if j > i:
                        next_nums.append(nums[i] + nums[j])
                    next_nums.append(nums[i] - nums[j])
                    next_nums.append(nums[i] * nums[j])
                    if nums[j] != 0:
                        next_nums.append(nums[i] / nums[j])
                    if any(dfs(next_nums)):
                        return True
        return False
    
    return dfs([float(num) for num in nums])

📌 23. 일일 온도

문제: 일일 기온(T)의 리스트가 주어졌을 때, 각 날짜에서 다음 따뜻한 날까지 며칠 기다려야 하는지를 반환하는 함수를 작성하세요. 만약 따뜻한 날이 없다면, 0으로 설정하세요.

input: [73, 74, 75, 71, 69, 72, 76, 73]
output: [1, 1, 4, 2, 1, 1, 0, 0]

def daily_temperatures(T: List[int]) -> List[int]:
    n = len(T)
    stack, result = [], [0] * n
    for i in range(n):
        while stack and T[i] > T[stack[-1]]:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

📌 24. 이진 트리의 중위 순회

문제: 이진 트리의 루트 노드가 주어졌을 때, 중위 순회(inorder traversal)를 구하는 함수를 작성하세요.

input: [1,null,2,3]
output: [1,3,2]

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root: TreeNode) -> List[int]:
    stack, result = [], []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        result.append(root.val)
        root = root.right
    return result

📌 25. 히스토그램에서 가장 큰 직사각형

문제: 히스토그램이 주어졌을 때, 이 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 함수를 작성하세요.

input: [2,1,5,6,2,3]
output: 10

def largest_rectangle_area(heights: List[int]) -> int:
    stack, max_area = [-1], 0
    for i in range(len(heights)):
        while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
            max_area = max(max_area, heights[stack.pop()] * (i - stack[-1] - 1))
        stack.append(i)
    while stack[-1] != -1:
        max_area = max(max_area, heights[stack.pop()] * (len(heights) - stack[-1] - 1))
    return max_area

📌 26. 저울

문제: 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 함수를 작성하세요.

input: [3, 1, 6, 2, 7, 30, 1]
output: 21

def can_measure_weight(weights: List[int]) -> int:
    weights.sort()
    max_weight = 0
    for weight in weights:
        if weight > max_weight + 1:
            break
        max_weight += weight
    return max_weight + 1

📌 27. 이퀄러이저

문제: 이퀄러이저 게임에서는 각각의 탑에 높이가 주어집니다. 각 탑에서는 자신보다 높은 탑으로 신호를 송신합니다. 이 때, 각 탑에서 송신된 신호를 수신하는 탑의 위치를 구하는 함수를 작성하세요.

input: [6, 9, 5, 7, 4]
output: [0, 0, 2, 2, 4]

def get_receiver_towers(heights: List[int]) -> List[int]:
    stack = []
    result = [0] * len(heights)
    for i in range(len(heights)):
        while stack and heights[stack[-1]] < heights[i]:
            stack.pop()
        if stack:
            result[i] = stack[-1]
        stack.append(i)
    return result

📌 28. 3의 배수

문제: 주어진 정수 배열 nums에서, 서로 다른 3개의 인덱스 (i, j, k)를 이용해 nums[i] + nums[j] + nums[k]가 3의 배수가 되는 개수를 구하는 함수를 작성하세요.

input: [1,2,3,4,5,6]
output: 5

def count_3_multiple_combinations(nums: List[int]) -> int:
    count = [0] * 3
    for num in nums:
        count[num % 3] += 1
    return (count[0] * (count[0] - 1) * (count[0] - 2) // 6 +
            count[1] * count[2] * (count[0] + count[2]) // 2 +
            count[1] * (count[1] - 1) * (count[1] - 2) // 6 +
            count[2] * (count[2] - 1) * (count[2] - 2) // 6)

📌 29. 다음 큰 숫자

문제: 어떤 양의 정수 n이 주어졌을 때, n의 다음 큰 숫자(next bigger number)는 다음과 같습니다.
1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.
예를 들어서, 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.
n이 주어질 때, n의 다음 큰 숫자를 리턴하는 함수를 작성하세요.

input: 78
output: 83

def get_next_bigger_number(n: int) -> int:
    binary_n = bin(n)[2:]
    count_n = binary_n.count('1')
    next_num = n + 1
    while True:
        binary_next = bin(next_num)[2:]
        count_next = binary_next.count('1')
        if count_next == count_n:
            return next_num
        next_num += 1

📌 30. 중복 문자 없는 가장 긴 부분 문자열

문제: 문자열 s가 주어졌을 때, s에서 중복된 문자가 없는 가장 긴 부분 문자열의 길이를 반환하는 함수를 작성하세요.

input: "abcabcbb"
output: 3

def length_of_longest_substring(s: str) -> int:
    max_len, start = 0, 0
    used = {}
    for i, char in enumerate(s):
        if char in used and start <= used[char]:
            start = used[char] + 1
        else:
            max_len = max(max_len, i - start + 1)
        used[char] = i
    return max_len

📌 31. 트리의 직경

문제: 트리의 루트 노드가 주어졌을 때, 트리의 두 노드 간 가장 긴 경로의 길이를 구하는 함수를 작성하세요. 경로는 경로 상에 있는 모든 노드들의 길이를 더한 값입니다.

input: [1,2,3,4,5]
output: 3

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameter_of_binary_tree(root: TreeNode) -> int:
    def depth(node: TreeNode) -> int:
        nonlocal diameter
        if not node:
            return 0
        left_depth = depth(node.left)
        right_depth = depth(node.right)
        diameter = max(diameter, left_depth + right_depth)
        return max(left_depth, right_depth) + 1

    diameter = 0
    depth(root)
    return diameter

📌 32. N개의 최소공배수

문제: n개의 숫자가 주어졌을 때, 이들의 최소공배수를 구하는 함수를 작성하세요.

input: [2,6,8,14]
output: 168

from math import gcd

def lcm(a: int, b: int) -> int:
    return a * b // gcd(a, b)

def get_n_lcm(nums: List[int]) -> int:
    while len(nums) > 1:
        nums.append(lcm(nums.pop(), nums.pop()))
    return nums[0]

📌 33. 문자열 압축

문제: 문자열 s가 주어졌을 때, s를 가장 짧게 압축한 문자열의 길이를 반환하는 함수를 작성하세요. 압축은 다음과 같은 방식으로 이루어진다.

• aabbaccc 와 같은 문자열은 2a2ba3c(1글자 이상 1000글자 이하)
• 압축된 문자열의 길이는 항상 짧아야 한다.

input: "aabbaccc"
output: 7

def compress_string(s: str) -> int:
    def compress(start: int, end: int) -> int:
        result = []
        count = 1
        for i in range(start + 1, end):
            if s[start:i] == s[i:i + (i - start)]:
                count += 1
            else:
                result.append(str(count) + s[start:i])
                count = 1
        result.append(str(count) + s[start:end])
        return len(''.join(result))

    if len(s) < 3:
        return len(s)
    answer = len(s)
    for i in range(len(s) // 2, 0, -1):
        start, end, step = 0, i, i
        result = compress(start, end)
        while end + step <= len(s):
            start, end = end, end + step
            result += compress(start, end)
        result += len(s) - end
        answer = min(answer, result)
    return answer

📌 34. 연속된 숫자 찾기

문제: 숫자로 이루어진 배열 nums가 주어졌을 때, 이 중에서 연속된 숫자로 이루어진 가장 긴 부분 배열의 길이를 반환하는 함수를 작성하세요.

input: [100, 4, 200, 1, 3, 2]
output: 4

def longest_consecutive(nums: List[int]) -> int:
    nums_set = set(nums)
    longest_length = 0
    for num in nums_set:
        if num - 1 not in nums_set:
            current_num = num
            current_length = 1
            while current_num + 1 in nums_set:
                current_num += 1
                current_length += 1
            longest_length = max(longest_length, current_length)
    return longest_length

📌 35. 벽돌 깨기

문제: 2차원 벽돌 배열과 구슬의 위치를 주어졌을 때, 구슬을 발사하여 맞은 벽돌들을 깨뜨릴 수 있는 최소 벽돌 수를 구하는 함수를 작성하세요. 벽돌을 깨뜨리는 방식은 다음과 같습니다.

1. 구슬을 발사하여 벽돌을 맞힌다.
2. 벽돌은 가로, 세로 방향으로 인접한 벽돌들과 함께 무너진다.
3. 무너진 벽돌들은 숫자 0을 나타낸다.
4. 빈 공간이 없도록 벽돌을 제거한다.
5. 제거된 벽돌의 수를 세어 최소 벽돌 수를 업데이트한다.

input:
grid = [[1, 0, 0, 0], [1, 1, 1, 0]]
hits = [[1, 0]]
output: [2]

def hit_bricks(grid: List[List[int]], hits: List[List[int]]) -> List[int]:
    def dfs(i: int, j: int) -> int:
        if not (0 <= i < rows and 0 <= j < cols) or grid[i][j] != 1:
            return 0
        grid[i][j] = 2
        res = 1
        for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            res += dfs(i + x, j + y)
        return res

    def is_connected(i: int, j: int) -> bool:
        if i == 0:
            return True
        for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nx, ny = i + x, j + y
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 2:
                return True
        return False

    rows, cols = len(grid), len(grid[0])
    for i, j in hits:
        grid[i][j] -= 1
    for j in range(cols):
        dfs(0, j)
    res = []
    for i, j in reversed(hits):
        grid[i][j] += 1
        if grid[i][j] == 1 and is_connected(i, j):
            res.append(dfs(i, j) - 1)
        else:
            res.append(0)
    return res[::-1]

📌 36. 미로 탐색

문제: 2차원 배열 maze와 출발점(start)과 도착점(destination)이 주어졌을 때, 출발점에서 도착점까지 도달하는 최소 이동 거리를 구하는 함수를 작성하세요. 단, 이동은 상하좌우로만 가능하며, 벽(#)은 통과할 수 없습니다.

input:
maze = [['#','#','#','#','#','#','#'],
        ['#','+','+','+','#','+','#'],
        ['#','+','#','+','#','+','#'],
        ['#','+','#','+','0','+','#'],
        ['#','#','#','#','#','#','#']]
start = (3, 4)
destination = (0, 1)
output: 8

def shortest_distance(maze: List[List[str]], start: Tuple[int, int], destination: Tuple[int, int]) -> int:
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    queue = deque([start])
    rows, cols = len(maze), len(maze[0])
    distance = [[float('inf')] * cols for _ in range(rows)]
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            count = 0
            while 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] != '#':
                nx += dx
                ny += dy
                count += 1
            nx -= dx
            ny -= dy
            if distance[x][y] + count < distance[nx][ny]:
                distance[nx][ny] = distance[x][y] + count
                if (nx, ny) != destination:
                    queue.append((nx, ny))
    return distance[destination[0]][destination[1]] if distance[destination[0]][destination[1]] != float('inf') else -1

📌 37. 기능 개발

문제: 각 기능별 개발 속도(progresses)와 개발이 완료된 날짜(day)가 주어졌을 때, 각 배포마다 몇 개의 기능이 배포되는지를 구하는 함수를 작성하세요. 각 기능은 진도가 100%일 때 함께 배포됩니다.

input: [93, 30, 55], [1, 30, 5]
output: [2, 1]

def get_release_count(progresses: List[int], speeds: List[int]) -> List[int]:
    days = []
    for i, progress in enumerate(progresses):
        days.append((100 - progress) // speeds[i] + (1 if (100 - progress) % speeds[i] != 0 else 0))
    res = []
    idx = 0
    while idx < len(days):
        count = 1
        for i in range(idx+1, len(days)):
            if days[i] <= days[idx]:
                count += 1
            else:
                break
        res.append(count)
        idx += count
    return res

📌 38. 유효한 괄호

문제: 주어진 문자열 s가 유효한 괄호 문자열인지 확인하는 함수를 작성하세요. 유효한 괄호 문자열은 아래 조건을 만족합니다.

• 열린 괄호는 같은 종류의 괄호로 닫혀야 합니다.
• 열린 괄호는 올바른 순서로 닫혀야 합니다.

input: "()"
output: True

input: "()[]{}"
output: True

input: "(]"
output: False

input: "([)]"
output: False

input: "{[]}"
output: True

def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

📌 39. 중복 문자 제거

문제: 주어진 문자열 s에서 중복된 문자를 제거하고 사전식 순서로 나열된 문자열을 반환하는 함수를 작성하세요.

input: "bcabc"
output: "abc"

input: "cbacdcbc"
output: "acdb"

def remove_duplicate_letters(s: str) -> str:
    last_occurrence = {c: i for i, c in enumerate(s)}
    stack = []
    for i, c in enumerate(s):
        if c in stack:
            continue
        while stack and stack[-1] > c and i < last_occurrence[stack[-1]]:
            stack.pop()
        stack.append(c)
    return ''.join(stack)

📌 40. 일일 온도

문제: 주어진 리스트 T에서 각 원소 i의 일일 온도 증가까지 며칠이 남았는지를 계산한 리스트를 반환하는 함수를 작성하세요. 만약 다음 온도가 없다면 0으로 설정합니다.

input: [73, 74, 75, 71, 69, 72, 76, 73]
output: [1, 1, 4, 2, 1, 1, 0, 0]

def daily_temperatures(T: List[int]) -> List[int]:
    res = [0] * len(T)
    stack = []
    for i in range(len(T)):
        while stack and T[stack[-1]] < T[i]:
            prev_idx = stack.pop()
            res[prev_idx] = i - prev_idx
        stack.append(i)
    return res

📌 41. 큐를 이용한 스택 구현

문제: 큐를 이용하여 스택을 구현하세요. 스택은 아래의 메소드를 지원해야 합니다.

• push(x): 요소 x를 스택에 삽입합니다.
• pop(): 스택의 첫 번째 요소를 삭제합니다.
• top(): 스택의 첫 번째 요소를 가져옵니다.
• empty(): 스택이 비어 있는지 여부를 반환합니다.

MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

class MyStack:
    def __init__(self):
        self.queue = collections.deque()

    def push(self, x: int) -> None:
        self.queue.append(x)
        for _ in range(len(self.queue)-1):
            self.queue.append(self.queue.popleft())

    def pop(self) -> int:
        return self.queue.popleft()

    def top(self) -> int:
        return self.queue[0]

    def empty(self) -> bool:
        return not self.queue

📌 42. 수식의 괄호 쌍

문제: 주어진 문자열 s가 올바른 수식의 괄호 쌍을 이루는지 판별하는 함수를 작성하세요. 올바른 수식의 괄호 쌍은 아래 조건을 만족합니다.

• 여는 괄호는 같은 종류의 괄호로 닫혀야 합니다.
• 괄호의 순서는 올바르게 구성되어야 합니다.

input: "()"
output: True

input: "()[]{}"
output: True

input: "(]"
output: False

input: "([)]"
output: False

input: "{[]}"
output: True

def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

📌 43. 백트래킹을 이용한 조합 구하기

문제: 리스트 nums와 정수 k가 주어졌을 때, nums에서 중복되지 않는 k개의 요소를 선택하여 만들 수 있는 모든 조합을 구하는 함수를 작성하세요.

input: nums = [1, 2, 3, 4], k = 2
output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

def combine(nums: List[int], k: int) -> List[List[int]]:
    def backtrack(start, curr):
        if len(curr) == k:
            output.append(curr[:])
        for i in range(start, len(nums)):
            curr.append(nums[i])
            backtrack(i + 1, curr)
            curr.pop()
    
    output = []
    backtrack(0, [])
    return output

📌 44. 문자열 압축

문제: 문자열 s를 압축하여 최대한 짧은 문자열로 만드는 함수를 작성하세요. 압축 규칙은 아래와 같습니다.

• 반복되는 문자열은 숫자와 해당 문자열로 표현합니다. 예를 들어, "aabccc"는 "2a3c"로 압축할 수 있습니다.
• 압축 후 문자열 길이가 더 길어진다면 원래 문자열을 반환합니다.

input: "aabcccccaaa"
output: "a2b1c5a3"

def compress_string(s: str) -> str:
    stack = []
    for c in s:
        if not stack or stack[-1][0] != c:
            stack.append([c, 1])
        else:
            stack[-1][1] += 1
    res = ""
    for c, cnt in stack:
        res += c
        if cnt > 1:
            res += str(cnt)
    return res if len(res) < len(s) else s

📌 45. 중복 문자 제거

문제: 문자열 s에서 중복된 문자를 제거하고 사전식 순서로 나열된 결과를 반환하는 함수를 작성하세요.

input: "bcabc"
output: "abc"

input: "cbacdcbc"
output: "acdb"

def remove_duplicate_letters(s: str) -> str:
    stack = []
    seen = set()
    last_occurrence = {c: i for i, c in enumerate(s)}
    for i, c in enumerate(s):
        if c not in seen:
            while stack and c < stack[-1] and i < last_occurrence[stack[-1]]:
                seen.remove(stack.pop())
            seen.add(c)
            stack.append(c)
    return ''.join(stack)

📌 46. 탑

문제: 수평 직선에 n개의 탑이 있습니다. 탑은 왼쪽으로만 레이저 신호를 보내며, 각 탑의 높이는 heights 리스트에 저장되어 있습니다. 신호는 탑의 높이와 같거나 높은 탑에서만 수신됩니다. 각 탑이 어느 탑에서 신호를 수신하는지를 나타내는 리스트를 반환하는 함수를 작성하세요. 만약 어떤 탑에서도 신호를 수신하지 못하는 경우, 0을 반환합니다.

input: heights = [6,9,5,7,4]
output: [0,0,2,2,4]

def find_building_receiving_signal(heights: List[int]) -> List[int]:
    stack = []
    res = [0] * len(heights)
    for i in range(len(heights)-1, -1, -1):
        while stack and heights[i] > heights[stack[-1]]:
            idx = stack.pop()
            res[idx] = i+1
        stack.append(i)
    return res

📌 47. 유효한 괄호

문제: 괄호로 이루어진 문자열 s가 주어졌을 때, 이 문자열이 유효한지 확인하는 함수를 작성하세요. 여기서 유효한 괄호란 아래 조건을 만족해야 합니다.

-열린 괄호는 반드시 같은 타입의 괄호로 닫혀야 합니다.

• 열린 괄호는 올바른 순서로 닫혀야 합니다.

input: "()"
output: True

input: "()[]{}"
output: True

input: "(]"
output: False

input: "([)]"
output: False

input: "{[]}"
output: True

def is_valid_parentheses(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else "#"
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

📌 48. 일일 온도

문제: 매일의 화씨 온도 T 리스트를 입력받아, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하는 함수를 작성하세요. 만약 더 따뜻한 날씨가 오지 않는다면, 0으로 출력하세요.

input: T = [73, 74, 75, 71, 69, 72, 76, 73]
output: [1, 1, 4, 2, 1, 1, 0, 0]

def daily_temperatures(T: List[int]) -> List[int]:
    stack = []
    res = [0] * len(T)
    for i in range(len(T)-1, -1, -1):
        while stack and T[i] >= T[stack[-1]]:
            stack.pop()
        if stack:
            res[i] = stack[-1] - i
        stack.append(i)
    return res

📌 49. 후위 표기식

문제: 후위 표기식으로 이루어진 문자열을 입력받아 계산한 결과를 출력하는 함수를 작성하세요. 후위 표기식은 연산자를 각 피연산자 뒤에 표기하는 표기법으로, 이 표기법은 괄호를 사용하지 않고도 연산의 우선순위를 자연스럽게 표현할 수 있습니다.

input: ["2", "1", "+", "3", "*"]
output: 9

input: ["4", "13", "5", "/", "+"]
output: 6

def eval_postfix(tokens: List[str]) -> int:
    stack = []
    for token in tokens:
        if token.isdigit():
            stack.append(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == "+":
                stack.append(operand1 + operand2)
            elif token == "-":
                stack.append(operand1 - operand2)
            elif token == "*":
                stack.append(operand1 * operand2)
            elif token == "/":
                stack.append(int(operand1 / operand2))
    return stack.pop()

📌 50. 중복 문자 제거

문제: 중복된 문자를 제외하고 사전식 순서로 나열한 결과를 반환하는 함수를 작성하세요.

input: "bcabc"
output: "abc"

input: "cbacdcbc"
output: "acdb"

def remove_duplicate_letters(s: str) -> str:
    last = {char: i for i, char in enumerate(s)}
    stack = []
    for i, char in enumerate(s):
        if char not in stack:
            while stack and char < stack[-1] and i < last[stack[-1]]:
                stack.pop()
            stack.append(char)
    return ''.join(stack)