Stack13 [자료구조] 사전순 부분문자열 파이썬 from itertools import combinations def solution(s): s = list(s) big = max(s) # print(big) for i in range(1, len(s)+1): C = combinations(list(s),i) C = ["".join(x) for x in list(C)] big = max(C+ [big]) return big max는 iterable로 받기 때문에 C와 big을 리스트로 변환한것을 하나의 list로 해서 넘겨줘서 해결이 되었는데 시간 초과가 발생함 combination이랑 max쪽에서 발생한거 같은데 앞선 문제처럼 heap으로 풀어야 하나. 이것도 stack 이용하면 풀린다... 순서를 요구한다면 for문을 사용한 stack을 생각해야 .. 2021. 4. 23. [자료구조] 짝지어 제거하기 파이썬 (stack, valid pair) def solution(s): stack = [] for i in s: if len(stack) == 0: stack.append(i) elif stack[-1] == i: stack.pop() else: stack.append(i) return (0,1)[len(stack) == 0] 단순 stack 문제였는데 너무 복잡하게 생각했다 valid parentheses랑 똑같은 건데 ㅠㅠ 마지막 return에서 tuple로 한 부분은 if-else를 쓰는 대신에 간결하게 표현이 가능하다. 예전에 LeetCode에서 봤던 표현식 그 때는 왜 tuple로 쓰는지 몰랐는데 지금보니 간결하게 표현이 가능하고 또한 return 값으로 T/F 대신 1/0으로 받는 문제의 경우가 있기 때문인듯. 2021. 4. 22. [자료구조] 대중소 괄호 짝 맞추기 파이썬 (stack, valid parentheses) stack의 대표적 문제니까 다시 또 체크 3.28일에 풀었네 (link) 이건 물론 다른 사람의 풀이 def solution(s): stack = [] # Hash map for keeping track of mappings. This keeps the code very clean. # Also makes adding more types of parenthesis easier mapping = {")": "(", "}": "{", "]": "["} # For every bracket in the expression. for char in s: # If the character is an closing bracket if char in mapping: # Pop the topmost element fro.. 2021. 4. 22. [자료구조] 중위 표현 수식 -> 후위 표현 수식 스택 파이썬 class ArrayStack: def __init__(self): self.data = [] def size(self): return len(self.data) def isEmpty(self): return self.size() == 0 def push(self, item): self.data.append(item) def pop(self): return self.data.pop() def peek(self): return self.data[-1] prec = { '*': 3, '/': 3, '+': 2, '-': 2, '(': 1 } def solution(s): opStack = ArrayStack() answer = "" for op in s: # 닫는 괄호를 만나는 경우 if op == ")":.. 2021. 4. 21. [자료구조] 스택 파이썬(LeetCode, Programmers) class ArrayStack: def __init__(self): self.data = [] def size(self): return len(self.data) def isEmpty(self): return self.size() == 0 def push(self, item): self.data.append(item) def pop(self): return self.data.pop() def peek(self): return self.data[-1] def solution(expr): match = { ')': '(', '}': '{', ']': '[' } S = ArrayStack() for c in expr: if c in '({[': S.push(c) elif c in match: if S.size.. 2021. 4. 20. [LeetCode] Valid Parentheses 파이썬 (stack, empty stack) class Solution: def isValid(self, s: str) -> bool: stack = [] for c in s: if len(stack) == 0: # 최초에 stack이 비었더라도 loop진행중 stack이 비워지면 다시 채워넣기 stack.append(c) elif stack[-1] == "{" and c == "}": stack.pop() elif stack[-1] == "[" and c == "]": stack.pop() elif stack[-1] == "(" and c == ")": stack.pop() else: stack.append(c) if len(stack) == 0: return True else: return False 방법은 맞았는데 계속 index 에러가 난 .. 2021. 3. 28. [프로그래머스] 짝지어 제거하기 파이썬 (stack, pop) 다른 사람의 풀이 def solution(s): stack = [] stack.append(s[0]) for i in s: if len(stack) == 0: # 최초에 stack이 비었더라도 loop진행중 stack이 비워지면 다시 채워넣기 stack.append(i) elif stack[-1] == i: stack.pop() else: stack.append(i) if len(stack) == 0: return 1 pair 로 하는 문제는 괄호같은 경우도 그렇고 stack으로 pop [프로그래머스] 올바른 괄호 파이썬 ygseo.tistory.com/163 2021. 3. 16. [프로그래머스] 올바른 괄호 파이썬 stack 비우기 다른사람의 풀이 def solution(s): answer = True stack = [] for i in s: if i == '(': stack.append('(') else: try: stack.pop() except: return False if len(stack) == 0: return True else: return False 출처: eda-ai-lab.tistory.com/478 2021. 3. 15. [프로그래머스] 큰 수 만들기 다른 사람의 풀이 def solution(number, k): # stack에 입력값을 순서대로 삽입 stack = [number[0]] for num in number[1:]: # 들어오는 값이 stack 값보다 크면, 기존의 값을 제거하고 새로운 값으로 바꿈 # 참고 : len(stack) > 0 == stack while len(stack) > 0 and stack[-1] 0: # 값을 한개 빼서 k는 1이 제거 k -= 1 # 내부의 값을 제거 stack.pop() # 새로운 값을 삽입 stack.append(num) # 만일 충분히 제거하지 못했으면 남은 부분은 단순하게 삭제 # 이렇게 해도 되는 이유는 이미 큰 수부터 앞에서 채워넣었기 때문 if k != 0: stac.. 2021. 3. 4. 이전 1 2 다음