archives

1995 https://leetcode.com/problems/count-special-quadruplets/ easy문제인데 O(n^2)의 시간복잡도로 풀려고 생각해보자. a+b+c=d가 나와야 하는데 c를 넘기면 a+b=d-c로 만들수 있다. 그리고 요 두파트를 각각 계산하면 된다. https://leetcode.com/problems/count-special-quadruplets/discuss/1446988/JavaC%2B%2BPython3-Real-O(n2)-solution class Solution: def countQuadruplets(self, nums: List[int]) -> int: # a + b = d - c d = {} ret = 0 n = len(nums) for i in rang..

1763 https://leetcode.com/problems/longest-nice-substring/ easy 로 분류되었는데 medium 하위정도 되는것같다. O(n^2)으로 모든 경우를 탐색한다. 길게 좌우에서 조여오면서 탐색한다. cur_s는 l과 r이 움직임에 따라 만들어지는 부분적인 문자열이고, cur_s내의 모든 문자가 대문자와 소문자가 cur_s내에 존재해야 하면서 이게 이전 길이보다 더 길면 바꿔준다. class Solution: def longestNiceSubstring(self, s: str) -> str: len_s = len(s) l = 0 ret = '' while l < len_s: r = len_s - 1 while l < r: cur_s = s[l:r+1] if all(..

974 https://leetcode.com/problems/subarray-sums-divisible-by-k/ subarray의 합이 k로 나눠지는 subarray를 구해야하는데 인덱스와 상관없이 구하는게 아니라 근처의 값들로만 구성해야 해서 백트래킹같은게 아니다. 앞에서부터 prefix sum을 계산해주며 prefix sum이 k로 나눠지면 그 값이 존재하는만큼 더해준다. 그리고 뒤에서도 사용하기 위해 그 값이 나온만큼 증가시켜준다. class Solution: def subarraysDivByK(self, nums: List[int], k: int) -> int: ret = 0 d = {0: 1} prefix_sum = 0 for i in range(len(nums)): prefix_sum += ..

2024 https://leetcode.com/problems/maximize-the-confusion-of-an-exam/ 바로 앞글의 1004번 문제랑 똑같다. 근데 이번엔 T나 F의 최대값으로 만들어야 한다. 그러면 간단하게는 T일경우의 최댓값과 F일경우의 최댓값을 구해서 그중에 최댓값을 리턴하면 된다. class Solution: def maxConsecutiveAnswers(self, ans: str, k: int) -> int: #ans = 'TFFT' #k = 1 l,r = 0,0 d = {'T':0, 'F':0} ret = 0 while r k and d['F'] > k: # l과 r사이, 즉 ..

935 https://leetcode.com/problems/knight-dialer/ 미리 다음에 갈수 있는 길들을 저장해놓는다. 그리고 n번만큼 반복해주면서 메모이제이션으로 한번 했던 계산은 하지 않도록 조절한다. class Solution: def knightDialer(self, n: int) -> int: #n=3131 d = {-1: range(10), 0: [4,6], 1: [6,8], 2: [7,9], 3: [4,8], 4: [0,3,9], 5: [], 6: [0,1,7], 7: [2,6], 8: [1,3], 9: [2,4]} cache = {} def dp(n, path): if n == 0: return 1 key = (n, path) if key in cache: return cach..

1405 https://leetcode.com/problems/longest-happy-string/ 단순히 dfs로 짜면 시간초과가 나왔다. 더 효율적으로 생각해보다가 가장 긴 길이를 만들어내려면 현재 존재하는 a,b,c중에서 가장 많이 존재하는 단어를 먼저 사용하는 전략으로 결과값을 만들어야 한다. 단어와 단어 카운트를 기반으로 힙을 만들어준 후 남아있는 단어중 갯수가 가장 많이 남아있는것부터 빼서 계산하는식으로 처리한다. from heapq import * class Solution: def longestDiverseString(self, a: int, b: int, c: int) -> str: s = '' while a > 0 or b > 0 or c > 0: heap = [] if a > 0 a..

39 https://leetcode.com/problems/combination-sum/ 별다른 설명이 필요 없다. 백트래킹 연습용으로 좋은 문제다. class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: #candidates = [1,2] #target = 4 ret = [] def get_comb(candidates, cand, target): if target == 0: ret.append(cand) return for i in range(len(candidates)): if target-candidates[i] >=0: get_comb(candidates[i:], cand + [c..

1209 https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/ 딱봐도 스택문제다. 새 문자가 들어올때마다 새 문자와, 새 문자가 존재하는 갯수를 넣어두고, 동일한 문자가 들어오면 카운트를 증가시켜준다. 이후 마지막 문자가 k보다 큰 경우 연산을 해준다. class Solution: def removeDuplicates(self, s: str, k: int) -> str: #s = "deeedbbcccbdaa" #k = 3 ret = '' stack = [] for i in range(len(s)): if stack and s[i] == stack[-1][0]: # 이미 들어왔던 문자의 경우 카운트를 늘려준다. stack[-1..

244 https://leetcode.com/problems/shortest-word-distance-ii/ 모든 word의 인덱스를 저장해놓는다. 그리고 구해야 하는 두 점에 대해서 투 포인터로 가장 근접해 있는 점 끼리의 최소값을 업데이트해준다. class WordDistance: def __init__(self, wd: List[str]): self.d = {} for i, w in enumerate(wd): self.d[w] = self.d.get(w, []) + [i] #print(self.d) def shortest(self, w1: str, w2: str) -> int: ret = 9999999999 i,j = 0,0 d1,d2 = self.d[w1],self.d[w2] while i < l..

227 https://leetcode.com/problems/basic-calculator-ii/ 이전 부호의 상태값을 저장해놨다가 그걸 기반으로 푼다. 이런 계산기반의 문제는 보통 부호를 한번 저장해놓고 다음단계에 가져와서 쓰는식으로 하는것 같다. 하드문제인 https://leetcode.com/problems/basic-calculator/ 와 비교해보면서 익히자. class Solution: def calculate(self, s: str) -> int: num = 0 stack = [] sign = '+' i = 0 while i < len(s): #print(s[i],stack) if s[i].isdigit(): num = num * 10 + int(s[i]) if s[i] in '+-*/' o..

1762 https://leetcode.com/problems/buildings-with-an-ocean-view/ 왼쪽에서부터 검사하면 오른쪽에 높은 벽이 나타났을때 다시 왼쪽의 케이스를 체크해야한다. 그런데 오른쪽에서부터 왼쪽으로 가면서 하면 다시 오른쪽의 케이스를 체크할 필요가 없다. 오른쪽에서 왼쪽으로 가면서, 최대값을 유지해주고 현재까지의 최대 높이보다 높아지는 왼쪽 높이가 나오면 그 인덱스를 저장해두면 된다. class Solution: def findBuildings(self, h: List[int]) -> List[int]: cur_max = 0 ret = [] for i in range(len(h)-1, -1, -1): if h[i] > cur_max: ret.append(i) cur_m..

986 https://leetcode.com/problems/interval-list-intersections/ 왠지 그리디 문제같이 생긴 list intersection문제이다. 무식하게 풀면 안되고 규칙을 찾은 뒤에 구현하면 된다. 투 포인터를 쓰기는 하는데 그냥 구현하면 된다.. 두개의 리스트가 있을때 겹치는 경우는 first_start List[List[int]]: diagonal_dict = {} for i in range(len(mat)): for j in range(len(mat[0])): if i-j not in diagonal_dict: diagonal_dict[i-j] = [] diagonal_dict[i-j].append(mat[i][j]) #for k,v in diagonal_dic..

2023 https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/ 요건 제한조건이 너무 단순해서 그냥 마음가는대로 이중 반복문으로 풀수도있지만 그랬다가는 알고리즘 공부하는 의미가 없다. nums리스트에서 두개만 앞값 + 뒷값으로 문자열을 연결했을때 target이 나오면 된다. prefix, suffix 딕셔너리를 만들어서 풀수 있는데, prefix 딕셔너리에는 앞에서 얼마만큼 만들었는지를 저장하고, suffix 딕셔너리에는 뒤에서 얼마만큼 만들었는지를 저장해둔다. nums = ["123","4","12","34"], target = "1234" 인 경우를 예로 보면 target 1234에 대해서 ..

160 https://leetcode.com/problems/intersection-of-two-linked-lists/ easy난이도인데 맨 아래의 제한조건이 O(n) 시간복잡도, O(1) 공간복잡도이다. 이거 생각하면서 풀려면 어렵다. 예제들을 살펴보면 교차로부터는 값이 전부 동일한걸 알수있다. input a,b중에 길이가 긴 링크드 리스트를 짧은 링스크 리스트랑 길이를 맞춰줄만큼 앞으로 전진해서 탐색을 시작한다. 둘다 똑같이 한칸씩 전진하면서, 값이 같으면 그걸 리턴해주고, 같은 값이 없으면 아무것도 리턴해주지 않으면 된다. class Solution(object): def getIntersectionNode(self, headA, headB): len_a, len_b = 0, 0 t_headA, ..

1638 https://leetcode.com/problems/count-substrings-that-differ-by-one-character/ 제한조건이 s와 t가 둘다 길이가 100이하이니 그냥 되는대로 구현하면 된다. s의 substring이 t의 substring안에 속하는데 하나만 달라야 한다. class Solution(object): def countSubstrings(self, s, t): #s = "aba" #t = "baba" len_s, len_t = len(s), len(t) ret = 0 for i in range(len_s): for j in range(len_t): diff, k = 0, 0 #print i,j while k+i < len_s and k+j < len_t: #..

1823 https://leetcode.com/problems/find-the-winner-of-the-circular-game/ 딱봐도 문제가 원형 이중연결리스트처럼 생겨서 이걸 만들어서 풀었다. 근데 시간이 많이 느리다.. 뭐지 하고 다른 답을 봤는데 아주 예전에 풀었던 조세퍼스(요세푸스) 문제였다. https://qkqhxla1.tistory.com/707 본지 하두 오래돼서 잊어먹고 있었다. 원형 이중연결리스트. class Node: def __init__(self, v): self.val = v self.next = None self.prev = None class Solution(object): def findTheWinner(self, n, k): start_node = cur_node = ..

617 https://leetcode.com/problems/merge-two-binary-trees/ 재귀 연습하기 좋은 기초문제다. 이런 비슷한 문제를 앞에서 여러번 풀어봤지만 그래도 좋다고 생각해서 가져온다.. class Solution(object): def mergeTrees(self, t1, t2): if not t1 or not t2: # 둘중 하나가 없으면 있는 노드 리턴 return t1 or t2 node = TreeNode(t1.val + t2.val) node.left = self.mergeTrees(t1.left, t2.left) node.right = self.mergeTrees(t1.right, t2.right) return node 1351 https://leetcode.co..

1261 https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/ 이진 트리가 오염되었다고 하고 복구를 먼저 한다음 풀라고 한다. 복구 조건은 루트값은 0부터 시작해서 왼쪽 자식은 2*부모+1, 오른쪽 자식은 2*부모+2이다. init에서 복구하면서 존재하는 값들을 set에 넣어준 후 계산하면된다. class FindElements(object): def __init__(self, root): self.val_set = set() queue = [[root, 0]] while queue: n, n_value = queue.pop(0) n.val = n_value self.val_set.add(n_value) if n.left: ..

1845 https://leetcode.com/problems/seat-reservation-manager/ 예약, 예약취소기능을 구현해야하고, 예약시에는 현재 예약가능한 좌석중에서 가장 번호가 낮은 좌석을 예약한다. == 현재 리스트에서 항상 가장 번호가 낮은 좌석을 가져오려면 힙을 만들어서 pop만 해주면 된다. 예약취소시에 새로 들어온 숫자까지 합쳐서 매번 정렬하는것보다는 힙으로 구현하는게 더 시간복잡도가 적게걸린다. import heapq class SeatManager(object): def __init__(self, n): self.available_seat = range(1, n+1) heapq.heapify(self.available_seat) def reserve(self): return..

110 leetcode.com/problems/balanced-binary-tree/ 문제를 이해하는데 시간이 좀 걸렸다. 모든 노드에서 각각의 서브트리의 높이 차가 1 초과로 나면 안된다. 1까지의 높이차이는 balanced되었다고 판별한다. 각각의 서브트리를 판별해야 하므로 재귀적으로 풀어야 한다. class Solution(object): def isBalanced(self, root): if not root: return True def check(root): if not root: return 0 l = check(root.left) r = check(root.right) if l == -1 or r == -1 or abs(l - r) > 1: # 좌,우 자식의 높이차가 1 초과로 나면 -1을 ..

763 leetcode.com/problems/partition-labels/ 글자들이 한묶음씩 묶여있다. 이걸 최대한 나눠줘야 한다. 모든 단어의 가장 오른쪽 인덱스를 저장해놓고, 하나씩 반복하면서 '여태까지 나온 글자중에 가장 오른쪽에 있는 글자' 가 현재 위치이면 이 인덱스가 하나의 파티션의 끝이 되므로, 이것과 현재 인덱스가 같으면 인덱스를 계산해서 넣어준다. class Solution(object): def partitionLabels(self, S): ret = [0] index_dict = {c:i for i,c in enumerate(S)} max_last_index = 0 for i, c in enumerate(S): max_last_index = max(max_last_index, in..

605 leetcode.com/problems/can-place-flowers/ 꽃을 심는데 반드시 꽃 사이사이에 한칸씩 공간이 있어야 한다. class Solution(object): def canPlaceFlowers(self, fb, n): i = 0 while i 0: if i == len(fb) -1 and fb[i-1] == 0 and fb[i] == 0: fb[i] = 1 n -= 1 break elif i < len(fb) -1 and fb[i] == 0 and fb[i+1] == 0: fb[i] = 1 n -= 1 i += 2 elif i < len(fb) -1 and fb[i] == 1 and fb[i+1] == 0: i += 2 else: i += 1 ..

1769 leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/ boxes배열이 있고, 1이면 공이 있고 0이면 공이 없다. i번째 배열에 모든 공을 모으려면 몇번 움직여야 하는지 합을 리턴하면 된다. 근데 당연히 무식하게 O(n^2)으로 하는게 의도가 아니라 O(n)으로 가능하다. 좋은 해설 : leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/discuss/1075895/Easy-Python-beats-100-time-and-space class Solution(object): def minOperations(self..

509 leetcode.com/problems/fibonacci-number/ 알고리즘 공부 시작하는 처음에 가장 먼저 배우는 쉬운거 class Solution(object): def fib(self, n): if n == 0: return 0 f = [0] * (n+1) f[1] = 1 for i in xrange(2, n + 1): f[i] = f[i-1] + f[i-2] return f[n] 복습용으로 읽어보는게 더 좋다 : leetcode.com/problems/fibonacci-number/discuss/215992/Java-Solutions 1137 leetcode.com/problems/n-th-tribonacci-number/ 위랑 똑같음. class Solution(object): def..

1041 https://leetcode.com/problems/robot-bounded-in-circle/ 명령어들을 반복했을때 로봇의 이동경로가 서클을 이루는지를 판별하는 문제이다. 오랫만에 푸느라 그런지 어떻게 풀어야 할지 감이 안잡혔는데... discussion을 보니 1. 명령을 다 실행하고 0,0으로 되돌아오면 서클을 이룸. 2. 또는 명령을 다 실행했는데 이동 방향이 북쪽이 아니면 명령을 반복하면 다시 처음으로 되돌아옴. 이라고 한다. 2번을 떠올리려면 직관력이 뛰어놔야 할듯 싶다. 명령이 다 끝났는데도 0,0이 아니고 이동 방향이 북쪽이면 위로만 계속 올라가게되니 아닌거고, 다 끝나고 방향이 왼쪽이면 시계 반대방향으로 돌면서 0,0으로 돌아오고, 오른쪽이면 시계 방향으로 돌면서 0,0으로 오..

787 https://leetcode.com/problems/cheapest-flights-within-k-stops/ 아주 오랫만에 보는 다익스트라 문제다. 기존에 풀던 다익스트라와 차이를 적자면, K번 stop이라는 횟수제한이 있어서 이 제한조건을 충족시켜야 한다. from collections import deque class Solution(object): def findCheapestPrice(self, n, flights, src, dst, K): adj = [[] for i in xrange(n)] for s,e,w in flights: adj[s].append([e, w]) dist = [float('inf') for i in xrange(n+1)] dist[src] = 0 q = dequ..

120 https://leetcode.com/problems/triangle/ 위에서부터 내려오면서 최소 값들을 triangle리스트에 업데이트해준다. 그리고 맨 마지막까지 끝났을때 거기서 최소값을 리턴한다. class Solution(object): def minimumTotal(self, triangle): if not triangle: return for i in xrange(1, len(triangle)): for j in xrange(len(triangle[i])): if j == 0: triangle[i][j] += triangle[i-1][j] elif j == len(triangle[i])-1: triangle[i][j] += triangle[i-1][j-1] else: triangle[i..

https://leetcode.com/problems/partition-equal-subset-sum/ 문제를 못풀었다. discussion에서 답들을 읽어보다 이 백트래킹 답이 가장 이해하기 쉬워서 이걸 공유한다.https://leetcode.com/problems/partition-equal-subset-sum/discuss/90610/Python-Backtracking-with-Memoization-Solution 답을 봐도 좀 빡세서 이해하는데 한참걸렸다. class Solution(object): def canFindSum(self, nums, target, ind, n, d): # 남은 nums배열, target, index, 끝길이, d=캐시 if target in d: return d[ta..

653 https://leetcode.com/problems/two-sum-iv-input-is-a-bst/ https://qkqhxla1.tistory.com/1055 여기서 1번, 167번의 2 sum을 풀었었는데 이번엔 단순히 트리에서 검색하는거다. 검색부만 트리로 변경한다. from collections import deque class Solution(object): def findTarget(self, root, target): queue = deque([root]) d = set() while queue: node = queue.popleft() if target - node.val in d: return True d.add(node.val) if node.left: queue.append(..

399 https://leetcode.com/problems/evaluate-division/ 처음에 이게 bfs dfs탐색으로 풀수있는문제인지 아예 감을 못잡았다. discussion중에https://leetcode.com/problems/evaluate-division/discuss/88275/Python-fast-BFS-solution-with-detailed-explantion 가 가장 유용했다. 요약하면 a/b가 2.0이면 a에서 b로 가는데 가중치가 2.0이라고 그래프형태로 저장해놓을수 있다. b/a는 0.5로 거꾸로도 저장해놓고 이런식으로 갈수있는 모든 경우의 수를 저장해놓는다. 그후에 갈수있는 이웃들을 전부 탐색하면서 해당 이웃으로 갈수 있으면 현재 값에 이웃으로 갈수 있는 가중치를 곱해주..