[BAEKJOON]백준 10799번 쇠막대기 - 스택(stack) 자료구조
백준 10799번 쇠막대기 백준 10499번 쇠막대기 코드 import sys input = sys.stdin.readline bar_razor = list(input().rstrip()) answer = 0 stack = [] for i in range(len(bar_razor)): # '('일 경우 계속 스택에 저장 if bar_razor[i] == '(': stack.append('(') else: #()라면 (를 pop하고 현재 스택에 들어있는 ( 수만큼 값을 더해준다. if bar_razor[i-1] == '(': stack.pop() answer += len(stack) else: stack.pop() #끄트머리 막대기 부분을 더해준다 answer += 1 print(answer)
[BAEKJOON]백준 10773번 제로 문제 파이썬(Python) 풀이 - 스택(Stack) 자료구조, 알고리즘(Algorithm)
문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할..
[BAEKJOON]백준 10828번 스택 문제 파이썬(Python) 풀이 - 스택(Stack) 자료구조, 알고리즘(Algorithm)
문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보..
[BAEKJOON]백준 9012번 괄호 문제 파이썬(Python) 풀이 - 문자열 조작, 스택 자료구조 알고리즘(Algorithm)
문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..
[Leetcode] 리트코드 - 빗물 트래핑(trapping-rain-water) 파이썬(python) 풀이
문제 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 입력 : height = [0,1,0,2,1,0,1,3,2,1,2,1] 출력 : 6 입력 : height = [4,2,0,3,2,5] 출력 : 9 코드 from typing import List class Solution: def trapTwoPointer(self, height: List[int]) -> int: if not height: return 0 volume = 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] while left < right: left_max, right_max = max(left_max, heig..
문제 [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘순으로 방문한다. 입력 [["MUC", "LHR"], ["JFK", "MUC"], ["SF0", "SJC"], ["LHR", "SF0"]] 출력 ["JFK", "MUC", "SF0", "SJC"] 입력 [["JFK", "SF0"], ["JFK", "ATL"], ["SF0", "ATL"], ["ATL", "JFK"], ["ATL", "SF0"]] 출력 ["JFK", "ATL", "JFK", "SF0", "ATL", "SF0"] 코드 DFS from typing import List import collections class Solution: def findItinerary(s..
중복 문자 제거 문제 중복된 문자를 제외하고 사전식 순서로 나열하라. 예제1 입력 "bcabc", 출력 "abc" 예제2 입력 "cbacdcbc", 출력 "acdb" 코드 정답 # 재귀 class Solution: def removeDuplicateLetters(self, s: str) -> str: # 집합으로 정렬 for char in sorted(set(s)): suffix = s[s.index(char):] # 전체 집합과 접미사 집합이 일치할때 분리 진행 if set(s) == set(suffix): return char + self.removeDuplicateLetters(suffix.replace(char, '')) return '' # 스택 import collections class So..
연결 리스트를 이용한 스택 ADT 구현 코드 class Node: def __init__(self, item, next): self.item = item self.next = next class Stack: def __init__(self): self.last = None def push(self, item): self.last = Node(item, self.last) def pop(self): item = self.last.item self.last = self.last.next return item stack = Stack() stack.push(1) stack.push(2) stack.push(3) stack.push(4) stack.push(5) 헷갈린 부분 처음에 Stack 클래스가 만들어지면..