전체 글267 [자료구조] 배달 파이썬 (BFS, queue, Dijkstra, heap) from math import inf from collections import defaultdict, deque from itertools import product def solution(N, roads, K): answer = [inf, 0] + [inf for i in range(N-1)] # print(answer) # why 처음이 0이 아니라 inf로 설정했을까? -> zero 인덱스 문제를 편하게 하려고 map = defaultdict(list) # 리스트 형태로 받겠다. dist_map = [[inf for _ in range(N+1)] for _ in range(N+1)] # print(dist_map) # for road in roads: a,b,dist = road map[a].ap.. 2021. 4. 23. [자료구조] 문자열 압축 사본 파이썬 (👍) def solution(s): if len(s) == 1: return 1 res = [] cut_range = list(range(1, (len(s)//2)+1)) ans = "" for cut in cut_range: tmp = s[:cut] cnt = 1 for i in range(cut, len(s), cut): if tmp == s[i:i+cut]: cnt += 1 else: if cnt == 1: cnt = "" ans += str(cnt) + tmp cnt = 1 tmp = s[i:i+cut] if cnt == 1: cnt = "" ans += str(cnt) + tmp res.append(len(ans)) ans = "" return min(res) 저번에도 한번 도전했었는데 이번에도 역시.. 2021. 4. 23. [자료구조] 주사위 게임 파이썬 (product) from itertools import product def solution(monster, S1, S2, S3): l1 = list(range(1, S1+1)) l2 = list(range(1, S2+1)) l3 = list(range(1, S3+1)) prod = list(map(sum,product(l1, l2, l3))) print(prod) cnt = 0 for p in prod: if p + 1 in monster: cnt += 1 return int((len(prod)-cnt)/len(prod)*1000) 출처: velog.io/@rapsby/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A3%BC%EC%82%AC%EC%9C%84-%.. 2021. 4. 23. [자료구조] 사전순 부분문자열 파이썬 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. 이전 1 2 3 4 5 ··· 30 다음