# 문제 설명 문자열 s와 문자열들의 사전인 wordDict가 주어질 때, s를 wordDict의 단어들로 분할할 수 있으면 True를 반환해라. 단, wordDict 내의 단어들은 분할에서 여러 번 사용할 수 있다. # 입출력 예시 입력 출력 s = "leetcode" wordDict = ["leet", "code"] True s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] False # 코드 풀이 더보기 틀린 풀이 이지만, 생각했던 방식을 정리해보았다. 1. 각 문자마다 wordDict로 시작하는 문자가 있다면, 재귀로 찾아가며 문자열 끝에 도달하면 True를 반환. from collections import defaultdict c..

# 문제 설명 두 이진트리의 root가 주어질 때, 이들이 같은 트리인지 반환해라. # 입출력 예시 입력 출력 p = [1,2,3] q = [1,2,3] True p = [1,2] q = [1,null,2] False p = [1,2,1] q = [1,1,2] False # 코드 풀이 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[Tr..

# 문제 설명 n개의 원형으로 이어진 주유소들이 있다. 각 i번째 주유소에는 gas[i]만큼의 연료를 가지고 있다. 한도가 없는 연료 탱크를 가진 차를 가지고 있을 때, i에서 i+1번째의 주유소에 가기 위한 각 비용은 cost[i]다. 한 주유소에서 빈 연료 탱크를 가지고 여행을 떠나려고 한다. 시계방향으로 주유소들을 모두 한 번 돌 수 있으면 그 시작 주유소 index를, 아니면 -1을 반환해라. # 입출력 예시 입력 출력 gas = [1,2,3,4,5] cost = [3,4,5,1,2] 3 gas = [2,3,4] cost = [3,4,3] -1 # 코드 풀이 1. Brute Force- O(n^2) class Solution: def canCompleteCircuit(self, gas: List[..

# 문제 설명 n개의 괄호() 쌍이 주어질 때, 규칙에 맞게 잘 생성된 모든 괄호 조합을 반환해라. # 입출력 예시 입력 출력 3 ["((()))","(()())","(())()","()(())","()()()"] 1 ["()"] # 코드 풀이 1 class Solution: def generateParenthesis(self, n: int) -> List[str]: paths = [] def make_paths(path, cnt): if len(path) == n*2: # 모두 완성된 상태 paths.append(path[:]) return if cnt < 1: # '('개수가 다 들어간 상태 make_paths(path+')', cnt) return if path.count('(')-path.coun..

# 문제 설명 Trie (or Prefix tree)는 문자열 데이터셋을 효율적으로 저장하고 키값을 가져오기 위한 자료구조다. 이 자료구조의 다양한 응용으로는 자동 완성과 스펠링 체크가 있다. 다음 기능을 제공하는 Trie 클래스를 구현해라. void insert(string word) 은 word를 Trie에 삽입한다. boolean search(string word) 은 Trie에 word가 있는지를 반환한다. boolean startsWith(string prefix) 은 prefix로 시작하는 단어가 있는지를 반환한다. # 입출력 예시 입력 출력 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); trie.search("app"..

# 문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말한다. 명령어 기능 I 숫자 큐에 주어진 숫자를 삽입 D 1 큐에서 최대값 삭제 D -1 큐에서 최소값 삭제 이중 우선순위 큐가 연산할 명령들이 주어질 때, 모든 연산을 처리한 후 [최대값, 최소값]을 반환해라. 최대값, 최소값을 삭제하는 연산에서 해당하는 값이 2개 이상인 경우, 하나만 삭제한다. 빈 큐에 데이터를 삭제하는 연산이 주어질 경우, 해당 연산은 무시한다. 단, 처리한 후 큐가 비어있다면 -1을 반환한다. # 입출력 예시 입력 출력 ["I 16", "D 1"] [0, 0] ["I 7", "I 5", "I -5", "D -1"] [7, 5] # 코드 풀이 from heapq import heappush, heappop, n..