DC 228 [자료구조] 사전순 부분문자열 파이썬 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. [자료구조] 배상 비용 최소화 파이썬 (heap) def solution(no, works): # max_idx = works.index(max(works)) # works[works.index(max(works))] -= 1 while no > 0: # reach 0 exit max_idx = works.index(max(works)) works[max_idx] -= 1 no -= 1 return sum([x**2 if x > 0 else 0 for x in works]) return할때 0보다 큰 조건을 안넣어줘서 오답이 나온것 같아서 넣어줬더니 통과했다. 일단 여기까지는 했는데 효율성에서 통과를 못했다 시간을 줄일 수 있는 부분이 while문 안에서 해결되어야 될거 같은데 음. sorted로 사용하니까 통과하긴 하는데 오래걸리긴 한다. def so.. 2021. 4. 22. [자료구조] 스킬트리 파이썬 def solution(skill, skill_trees): cnt = 0 for skill_set in skill_trees: check = [] for s in skill_set: if s in skill: check.append(s) else: n = len(check) if list(skill)[:n] == check: cnt += 1 return cnt 스킬트리에 있는 각 element를 skill set이라고 하고 이 skill set에 있는 원소중에서 순회하면서 skill에 있는 원소만 꺼내면 순서도 그대로 유지하면서 꺼낼수 있을거라 생각해서 리스트로 꺼냈다 두 번째 for loop(skill set의 각 element 순회하면서 skill에 있는 원소만 꺼낸다.) 이 정상적으로 끝나면(el.. 2021. 4. 22. [자료구조] 올바른 괄호 파이썬 (valid parentheses, if~) def solution(s): if s[0] == ")": return False stack = [] for c in s: if not stack: if c == ")": return False else: stack.append(c) elif stack[-1] == "(" and c == ")": stack.pop() else: stack.append(c) return len(stack) ==0 stack이 비어있을 경우 다음 입력값이 close일 경우 False로 리턴 하는 조건을 추가해줬다 괄호 종류가 하나라서 그냥 mapping을 만들지 않고 진행했다. 2021. 4. 22. [자료구조] 세 소수의 합 파이썬 (prime number) from itertools import combinations def check(n): k = n**0.5 if n < 2: return False for i in range(2, int(k)+1): if n % i == 0: return False return True def solution(n): candidates = [] for i in range(2,n+1): if check(i): candidates.append(i) combi = combinations(candidates, 3) ans = 0 for c in combi: if sum(c) == n: ans += 1 return ans 2부터 n까지의 수 중에서 소수인 경우만 candidates 리스트로 저장 combinations 사용해서 .. 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. [자료구조] 좌석구매 파이썬 (hashable VS. unhashable) unique한 pair를 구하면 될거라 생각해서 2d 리스트를 그대로 set에 넣었지만 TypeError: unhashable type: 'list' unhashable 에러가 발생했다. 문제를 마저 풀기 전에 unhashable과 hashable의 차이점을 알아보자. 출처: realpython.com/lessons/immutable-vs-hashable/ hashable object라는 것은 can't modify 정도로 이해가 가능한데 좀 더 설명이 필요하기 때문에 다른 글을 찾아봤다. 요약: non-duplicate를 요구하는 python object들은 hashable하다. 출처: https://analytics4everything.tistory.com/m/138 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. 이전 1 2 3 4 다음
