문제 연결 리스트를 뒤집어라. 입력 : 1 → 2 → 3 → 4 → 5 → NULL 출력 : 5 → 4 → 3 → 2 → 1 → NULL 코드 """ fixme https://leetcode.com/problems/reverse-linked-list/ Q15. 역순 연결 리스트 연결 리스트를 뒤집어라. 입력 : 1 → 2 → 3 → 4 → 5 → NULL 출력 : 5 → 4 → 3 → 2 → 1 → NULL """ class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def reverseListRecur(self, head: ListNode) -> ListNode: def re..
문제 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 입력 : 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..
문제 당신은 전문털이범이다. 어느 집에서든 돈을 훔쳐올 수 있지만 경보 시스템 때문에 바로 옆집은 훔칠 수 없고 한 칸 이상 떨어진 집만 가능하다. 각 집에는 훔칠 수 있는 돈의 액수가 입력 값으로 표기되어 있다. 훔칠 수 있는 가장 큰 금액을 출력하라. 입력 : [1, 2, 3, 1] 출력: 4 설명 첫 번째 집에서 1, 세번째 집에서 3, 따라서 1 + 3 = 4 입력 : [2, 7, 9, 3, 1] 출력 : 12 설명 첫 번째 집에서 2, 세 번째 집에서 9, 다섯 번째 집에서 1, 따라서 2 + 9 + 1 = 12이다. 코드 """ fixme. https://leetcode.com/problems/house-robber/ fixme. Q88. 집도둑 fixme. 당신은 전문털이범이다. 어느 집에서..
문제 피보나치 수를 구하라. F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. 입력 : n = 2 출력 : 1 입력 : n = 3 출력 : 2 입력 : n = 4 출력 : 3 코드 """ fixme. https://leetcode.com/problems/fibonacci-number/ fixme. Q85. 피보나치 수 fixme. 피보나치 수를 구하라. fixme. 입력 : n = 2 fixme. 출력 : 1 """ import collections import numpy as np class Solution: def fib(self, N: int) -> int: if N int: if N int: self.dp[1] = 1 for i in range..
문제 숫자와 연산자를 입력 받아 가능한 모든 조합의 결과를 출력하라. 입력 : "2 - 1 - 1" 출력 : [0, 2] 설명 ((2 - 1) - 1) = 0 (2 - (1 - 1)) = 2 입력 : "2 * 3 - 4 * 5" 출력 : [-34, -14, -10, -10, 10] 설명 (2 * (3 - (4 * 5))) = -34 ((2 * 3) - (4 * 5)) = -14 ((2 * (3 - 4)) * 5) = -10 (2 * ((3 - 4) * 5)) = -10 (((2 * 3) - 4) * 5) = 10 코드 """ fixme. https://leetcode.com/problems/different-ways-to-add-parentheses/ fixme. Q84. 괄호를 삽입하는 여러 가지 방법..
문제 원형으로 경로가 연결된 주유소 목록이 있다. 각 주유소는 gas[i] 만큼의 기름을 갖고 있으며, 다음 주유소로 이동하는데 cost[i]가 필요하다. 기름이 부족하면 이동할 수 없다고 할 때 모든 주유소를 방문할 수 있는 출발점의 인덱스를 출력하라. 출발점이 존재하지 않을 경우 -1을 리턴하며, 출발점은 유일하다. 입력 : gas = [1,2,3,4,5], cost = [3,4,5,1,2] 출력 : 3 설명 3번 인덱스(기름을 4만큼 충전할 수 있는)에서 출발할 경우는 다음과 같다. 3번 → 4번 -1 fuel 3 4번 → 0번 -1 fuel 6 0번 → 1번 -1 fuel 4 1번 → 2번 -1 fuel 2 2번 → 3번 -1 fuel 0 정확하게 기름이 0까지 소모되며, 모든 주유소를 방문할 수..
문제 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라. 입력 : S = "AD0BEC0DEBANC", T = "ABC" 출력 : "BANC" 코드 """ fixme. https://leetcode.com/problems/minimum-window-substring/ fixme. Q76. 부분 문자열이 포함된 최소 윈도우 fixme. 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라. fixme. 입력 : S = "AD0BEC0DEBANC", T = "ABC" fixme. 출력 : "BANC" """ import collections class Solution: def minWindowPointer(self, s: str, t..
문제 두 정수 a와 b의 합을 구하라. +또는 -연산자는 사용할 수 없다. 입력 a = 1, b = 2 출력 3 입력 a = -2, b = 3 출력 1 코드 전가산기 구현 class Solution: def getSum(self, a: int, b: int) -> int: MASK = 0xFFFFFFFF INT_MAX = 0x7FFFFFFF a_bin = bin(a & MASK)[2:].zfill(32) b_bin = bin(b & MASK)[2:].zfill(32) result = [] carry = 0 sum = 0 for i in range(32): A = int(a_bin[31 - i]) B = int(b_bin[31 - i]) # 전가산기 구현 Q1 = A & B Q2 = A ^ B Q3 = Q..
문제 연결 리스트를 삽입정렬로 정렬하라. 코드 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def insertionSortList(self, head: ListNode) -> ListNode: cur = parent = ListNode(0) while head: while cur.next and cur.next.val head.val: cur = parent return parent.ne..
문제 연결 리스트를 O(n*logn)에 정렬하라. 입력 4 → 2 → 1 → 3 출력 1 → 2 → 3 → 4 코드 병합 정렬 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1 and l2: if l1.val > l2.val: l1, l2 = l2, l1 l1.next = self.mergeTwoLists(l1.next, l2) return l1 or l2 def sortList(self, head: ListNode) -> ListNode: if n..
문제 단어 리스트에서 words[i] + words[j]가 펠린드롬이 되는 모든 인덱스 조합(i, j)를 구하라. 입력 ["abcd","dcba","lls","s","sssll"] 출력 [[0,1],[1,0],[3,2],[2,4]] ["dcbaabcd","abcddcba","slls","llssssll"]이 팰린드롬이다. 입력 ["bat","tab","cat"] 출력 [[0,1],[1,0]] ["battab","tabbat"]이 팰린드롬이다. 코드 import collections from typing import List # 트라이 저장용 노드. class TrieNode: def __init__(self): self.children = collections.defaultdict(TrieNode) se..
문제 트리의 전위, 중위 순회 결과를 입력값으로 받아 이진 트리를 구축하라. 전위 순회 결과: [3,9,20,15,7] 중위 순회 결과: [9,3,15,20,7] 결과는 밑의 그림과 같은 이진 트리가 된다. 코드 from typing import List class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if inorder: # 전위 순회 결과는 중위 순회 분할 인덱스 index = ino..
문제 두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라. 입력 root = [4, 2, 6, 1, 3, null, null] 출력 1 노드 3과 노드 4의 값의 차이는 1이다. 입력 root = [10, 4, 15, 1, 8, null, null] 출력 2 이 경우 노드 간 값의 차이가 가장 작은 노드는 8과 10이다. 1과 4는 거리의 차이가 3이고, 4와 8은 차이가 4이지만 8과 10의 차이는 2로 최솟값이다. 코드 재귀 구조로 중위 순회 import sys class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solut..
문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 출력 2 입력 출력 2 코드 class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: result: int = 0 def longestUnivaluePath(self, root: TreeNode): def dfs(node: TreeNode): if node is None: return 0 left = dfs(node.left) right = dfs(node.right) if node.left and node.left.val == node.val: left += 1 else: l..
문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 다음과 같은 이진 트리가 주어졌을 때, 1 2 3 4 5 가장 긴 경로는 4 → 2 → 1 → 3 또는 5 → 2 → 1 → 3으로 3이다. 코드 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: longest: int = 0 def diameterOfBinaryTree(self, root: TreeNode) -> int: def dfs(node: TreeNode) -> int: # 리프노드의 left, right 노드를 None으로 초기화하므로 거기까지..
문제 K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값 (u, v, w)는 각각 출발지, 도착지, 소요시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다. 입력 times = [[2,1,1], [2,3,1], [3,4,1]], N = 4, K = 2 출력 2 코드 from typing import List import collections, heapq class Solution: def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int: graph = collections.defaultdict(list) for u, v, w in times: graph[u].append..
문제 입력 2, [[1,0]] 출력 True 입력 2, [[1,0],[0,1]] 출력 False 코드 visited 없을 때 from typing import List import collections class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = collections.defaultdict(list) for x, y in prerequisites: graph[x].append(y) traced = set() def dfs(i): if i in traced: return False traced.add(i) for y in graph[i]: if not dfs(y): ret..
문제 [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,2,3] 출력 [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 코드 재귀 함수 from typing import List class Solution: def permute(self, nums: List[int]) -> List[List[int]]: results = [] prev_elements = [] def dfs(elements): if len(elements) == 0: results.append(prev_elements[:]) for e in elements: next_elements = elements[:] next_elements.remove(e) prev_elem..
문제 전체의 수 n을 입력받아 k개의 조합을 리턴하라. 입력 : n = 4, k = 2 출력 [ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] ] 코드 dfs from typing import List class Solution: def combine(self, n: int, k: int) -> List[List[int]]: results = [] def dfs(elements, start: int, k:int): if k == 0: results.append(elements[:]) for i in range(start, n+1): elements.append(i) dfs(elements, i+1, k-1) elements.pop() dfs([], 1, k) return res..
전화 번호 문자 조합 문제 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라. 입력 : "23" 출력 : ["ad","ae","af","bd","be","bf","cd","ce","cf"] 코드 from typing import List class Solution: def letterCombinations(self, digits: str) -> List[str]: def dfs(index, path): if len(path) == len(digits): result.append(path) return for i in range(index, len(digits)): for j in dic[digits[i]]: dfs(i + 1, path + j) if not digits: r..
k개 정렬 리스트 병합 문제 k개의 정렬된 리스트를 1개의 정렬 리스트로 병합하라 입력 [1 → 4 → 5, 1 → 3 → 4, 2 → 6] 출력 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 코드 from typing import List import heapq class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: root = result = ListNode(None) heap = [] for i in range(len(lists)): if lists[i]: heapq.heappush(heap, ..
중복 문자 제거 문제 중복된 문자를 제외하고 사전식 순서로 나열하라. 예제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..
역순 연결 리스트 Ⅱ 문제 인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다. 입력 1→2→3→4→5→NULL, m = 2, n = 4 출력 1→4→3→2→5→NULL 코드 class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: if not head or m == n: return head root = start = ListNode(None) root.next = head for _ in range(m - 1): start = start.next end = star..
페어의 노드 스왑 문제 문제링크 연결 리스트를 입력받아 페어(pair) 단위로 스왑하라 입력 1→2→3→4 출력 2→1→4→3 코드 class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def swapPairs(self, head: ListNode) -> ListNode: root = prev = ListNode(None) prev.next = head while head and head.next: #fixme b가 head를 가리키도록 할당 b = head.next head.next = b.next b.next = head #fixme prev가 b를 가리키도록 할당 prev.next = b #fixme ..
두 수의 덧셈 문제 문제링크 역순으로 저장된 연결 리스트의 숫자를 더하라 입력 (2 → 4 → 3) + (5 → 6 → 4) 출력 7 → 0 → 8 코드 class ListNode: def __init__(self, x): self.val = x self.next = None class Solution(): def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: root = head = ListNode(0) carry = 0 while l1 or l2 or carry: sum = 0 if l1: sum += l1.val l1 = l1.next if l2: sum += l2.val l2 = l2.next carry, val = divmod(sum..
두 정렬 리스트의 병합 problem 문제링크 정렬되어 있는 두 연결 리스트를 합쳐라 입력 1→2→4 1→3→4 출력 1→1→2→3→4→4 solution 리트코드 정답 class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if (not l1) or (l2 and l1.val > l2.val): l1, l2 = l2, l1 if l1: l1.next = self.mergeTwoLists(l1.next, l2) return l1 풀이용 코드 class ListNode: def __init__(s..
팰린드롬 연결 리스트 문제 링크 code class ListNode(): def __init__(self, x): self.val = x self.next = None class Solution(): def isPalindrome(self, head: ListNode) -> bool: rev = None slow = fast = head while fast and fast.next: fast = fast.next.next rev, rev.next, slow = slow, rev, slow.next # 역순으로 연결 리스트 rev를 생성하는 로직을 slow 앞에 덧붙인다. if fast: slow = slow.next while rev and rev.val == slow.val: slow, rev = sl..
리트코드 Group Anagrams from typing import List import collections class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: anagrams = collections.defaultdict(list) for word in strs: anagrams[''.join(sorted(word))].append(word) print(anagrams) return anagrams.values() if __name__ == '__main__': s = Solution() print(s.groupAnagrams(["eat","tea","tan","ate","nat","bat"])) sorted()는..