728x90 코딩 테스트97 [LeetCode] 1092. Shortest Common Supersequence (Python) Problem SolutiondbLCS (Longest Common Subsequence)이 문제의 힌트를 보고 LCS 알고리즘을 사용한 문제라는 것을 알았다.LCS 알고리즘에 대한 설명은 다른 블로그에서 더 자세하게 설명해두어서 참고했다!https://chanhuiseok.github.io/posts/algo-34/ 알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘LCS 알고리즘이란?chanhuiseok.github.io 단 LCS 의 길이를 구하는 알고리즘이라서 LCS 문자를 찾으려면 역추적(back tracking)을 이용해서 구해야한다. 주어진 2개의 string의 LCS 를 구하는 규칙은 아래와 같다.문자열을 비교하여 같았을 때현재 칸에 들어.. 2025. 2. 28. [LeetCode] 873. Length of Longest Fibonacci Subsequence (Python) Problem Solutiondphashi, j를 피보나치 수열 마지막 두 숫자로 두고 dp[(i, j)] 에 해당 수열의 길이를 저장한다.해시맵 index_map 을 사용하여 빠르게 arr[k] 의 index를 찾을 수 있도록한다.해시셋을 이용하여 arr[i]+arr[j] in arr 여부를 확인한다.Bruteforce 로 풀면 time limit exceeded 나는 문제. db를 사용해서 풀어햐한다. (i, j)를 마지막 두 숫자로 하는 피보나치 수열 찾기!즉, arr[i], arr[j]를 고정하고, arr[i] + arr[j] == arr[k]가 되는 k를 찾아가야 합니다.이를 위해 j를 기준으로 i를 선택하고, (i, j) 쌍을 만들도록 설계합니다.반복문을 돌때 j부터 돌아서 항상 idb[(i,.. 2025. 2. 27. [LeetCode] Maximum Absolute Sum of any SubArray (Python) Problem SolutionKadane's algorithmsubArray 중 절대값 합의 최대값을 구하는 문제.2중포문으로 구현하면 당연히 time limit 이 발생한다.힌트 중에서 Kadane's 알고리즘을 사용하라고한다. 알아보았더니 dp 문제였다.Kadane's 알고리즘을 간략히 설명하면일반적인 Kadane’s Algorithm은 최대 연속 부분합을 구하는 알고리즘입니다.여기서는 최대 합과 최소 합을 동시에 추적하여, 그 절댓값 중 가장 큰 값을 반환하도록 변경합니다.현재까지의 max_sum/min_sum 을 현재 num과 비교하며 갱신한다.Kadane's 알고리즘 설명은 다른 블로그 설명을 참고했다.https://scavienger.tistory.com/19 [Algorithm] Kadane.. 2025. 2. 26. [LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal (Python) Problem Solutionarraybinary treerecursive preorder, postorder list 을 보고 binary tree을 구하는 문제. Code# 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 = rightclass Solution: def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode].. 2025. 2. 23. [LeetCode] 1980. Find Unique Binary String (Python) Problem Solutionbrute force 1, 0 으로 만들 수 있는 이진법 수 중 n=len(nums) 을 만족하는 배열 중 nums에 존재하지않는 string 반환하는 문제. Codeclass Solution: def findDifferentBinaryString(self, nums: List[str]) -> str: n = len(nums) chars = ["1", "0"] def generate(n, cur=""): if n==0: return [cur] res = [] res += generate(n-1, cur + "0") res += g.. 2025. 2. 22. [LeetCdoe] 1079. Letter Tile Possibilities (Python) Problem Solutionpermutationbacktracking DFS중복 순열을 사용한 문제.중복 허용, 순서 고려하여 모든 경우의수를 따져야하지만 만들어진 string이 중복되면안된다.permutation을 사용하되 결과를 set에 담아서 저장하도록했다. 백트래킹을 사용했지만 시간복잡도에서 최악의 경우 많이 소요될 수 있다.Codeimport itertoolsclass Solution: def numTilePossibilities(self, tiles: str) -> int: def generate(cur, used, result, r): if len(cur) == r: print(cur) result... 2025. 2. 20. [LeetCode] 1415. The k-th Lexicographical String of All Happy Strings of Length n (Python) ProblemSolutionrecursive, backtracking3개 문자중에서 n개 만큼 뽑는 순열문제.단, str[i] != str[i+1] 이어야한다. Codeclass Solution: def getHappyString(self, n: int, k: int) -> str: chars = ['a', 'b', 'c'] li = [] def happy(cur): # 문자열 길이가 n이면 종료 if len(cur) == n: li.append(cur) return for char in chars: .. 2025. 2. 19. [LeetCode] 2375. Construct Smallest Number From DI String (Python) Problem Solutionstackbrute forceI 가 나오면 숫자 증가,D 가 나오면 숫자가 감소하도록하여 가장 작은 수를 반환하는 문제.지난번 비슷한 문제에서 dfs 를 사용했어서 비슷하게 풀면되는 줄 알고 삽질함 사전적으로 가장 작은 숫자를 반환해야하므로 가장 작은 수인 1부터 숫자 추가.마지막 인덱스이거나 patter[i] == I 이면 stack 모두 비울때까지 res 배열에 넣는다. stack 이라서 FIFO 구조로 먼저 넣은 숫자 먼저 res에 저장된다. 마지막에 res 배열에 있는 숫자들 join 해주면됨! pattern의 길이가 8까지라서 hint에도 bruteforce로 다해보라고 권했음. Codeclass Solution: def smallestNumber(self, .. 2025. 2. 18. [LeetCode] 1718. Construct the Lexicographically Largest Valid Sequence (Python) ProblemSolutionbacktrackingheuristic (bruteforce)처음에 한번에 이해하는게 어려웠던 문제.조건은 아래와 같다.1 ~ n 까지의 수 중에서 1) 1 은 한번만 나옴2) 2~n 사이의 수는 2번 나옴3) 사전순으로 정렬했을 때 a[i] == a[j] 에 대해서 |j-i| = n 이어야한다. 예를들어 arr = [3, 1, 2, 3, 2] 에서 3은 2번 등장하고 두 거리는 3 이다. (arr[0] = 3, arr[3] = 3) 2는 2번 등장하고 두 거리는 2이다. (arr[2] = 2, arr[4] = 2)4) 사전순으로 정렬했을 때 가장 큰 배열 return이때 처음에 숫자를 넣을 때 n (가장 큰 수) 부터 배열에 넣는게 유리하다. Codeclass.. 2025. 2. 16. [LeetCode] 2698. Find the Punishment Number of an Integer (Python) Problem Solutionrecursive주어진 n 에 대해서 1 힌트를 보니 재귀로 해당 조건을 만족하는지 체크하는 내용이었다. sqared (제곱) 값을 구한 후 string 으로 변환한 뒤, 1 부터 i 까지 재귀함수를 돌며 조건을 만족하는지 체크한다. (check method)step 1) idx = 0 자리수부터 체크하되 idx == len(sqared) 길이가 동일해지면 지금까지의 합계와 target 값이 동일한지 체크 후 반환.step 2) 0 부터 len(sqared) 까지 각 자리수의 인덱스를 돌면서 합계를 구한다. 재귀함수를 통해서 1의 자리부터, 10의 자리부터, 100의 자리부터 계산해가며 target 값이 나올때까지 반복한다. Codeclass Solution: def .. 2025. 2. 15. [LeetCode] CodeTestcaseTestcaseTest Result1352. Product of the Last K Numbers (Python) Problem Solutionlistlist에서 마지막 K개 원소의 총 곱을 구하는 문제.시간복잡도가 O(N)이면 time out이 발생해서 O(1)으로 해결해야되는 문제!prefix 곱을 모두 구한 뒤, prefix[n-1] // prefix[n-k-1] 로 뒤에서 k개 원소의 곱을 구한다.여기서 문제는 분모가 0이되면 안된다.1) 모든 원소를 저장한 arr중 마지막 k개 원소만 담은 arr[-k:] 에 0이 포함되어있는지 체크2) k == len(arr[-k:]) 이면 prefix[-1] 마지막 값 반환3) 분모가 0이면 for문으로 직접 모두 계산 Codeclass ProductOfNumbers: def __init__(self): self.prefix = [] se.. 2025. 2. 14. [LeetCode] 3066. Minimum Operations to Exceed Threshold Value II (Python) Problem Solutionheapnums에서 k보다 작고 가장 작은 최소값 2개를 구해서 min(x,y) * 2 + max(x,y) 를 nums에 추가한다.이때 최소값 2개는 반드시 필요하다.위 반복 작업을 몇 번하는지 카운트하는 문제. Codeimport heapqclass Solution: def minOperations(self, nums: List[int], k: int) -> int: answer = 0 heapq.heapify(nums) while(len(nums) > 1 and nums[0] ComplexityTime Complexityheapq.heapify(nums) -> O(N) num1 = heapq.heappop(nums) # O(l.. 2025. 2. 13. [LeetCode] 2342. Max Sum of a Pair With Equal Sum of Digits (Python) Problem SolutionHash 보통 배열의 길이가 10^5 이하이면 2중 for문은 안쓰는게 상책. time out이 발생할 확률이 99%이기 때문어떤 index인지는 i != j 조건만 만족하면 되므로 nums를 먼저 오름차순으로 정렬 후 시작한다.동일한 sumDigit 을 가지는 인덱스를 hashMap으로 저장한 다음에 가장 마지막과 마지막에서 2번째 인덱스의 nums[i] + nums[j] 를 구하여 max 값을 갱신한다.가장 마지막과 2번째로 마지막 인덱스를 구하는 이유는 처음에 오름차순 정렬을 했으므로 가장 뒤쪽의 인덱스일수록 nums[i]가 큰 정수값이기 때문이다. Codeclass Solution: def maximumSum(self, nums: List[int]) -> int:.. 2025. 2. 12. [LeetCode] 1910. Remove All Occurrences of a Substring (Python) Problem Solutionstringpart에 해당하는 문자가 s 에 존재하지 않을 때까지 제거하는 문제.왜 replace를 생각하지 못했을까 ㅜㅜ class Solution: def removeOccurrences(self, s: str, part: str) -> str: while part in s: s = s.replace(part,"",1) return s시간복잡도 : O(N) , 최악의 경우 O(N^2)공간복잡도: O(N)Codeclass Solution: def removeOccurrences(self, s: str, part: str) -> str: idx = 0 n = len(part) whil.. 2025. 2. 11. [LeetCode] 3174. Clear Digits (Python) Problem Solutionstring, stack문자열 s에서 digit이 있으면 digit 과 그 왼쪽에있는 문자를 제거하는 문제 (반복).문자열을 순회하면서 해당 index를 기준으로 digit 여부와 왼쪽 문자를 체크하여 s 를 업데이트한 후 조건에 해당되지 않을 때까지 반복한다. 다른 코드에서는 alpha이면 list에 저장하고 그 다음 문자가 digit이면 pop하여 list에서 제거한 뒤 최종적으로 string으로 concat 해서 반환한다.class Solution: def clearDigits(self, s: str) -> str: stack = [] for char in s: if char.isdigit(): .. 2025. 2. 10. [LeetCode] 2364. Count Number of Bad Pairs (Python) ProblemSolutionHashMapi bad pair 정의 if i bad pair의 쌍 개수 구하기관점을 바꿔서 i - nums[i] == j - nums[j] 인 good pairs를 구한 뒤 전체 - good pairs를 구한다.즉, nums[i] - i 값이 동일한 숫자끼리 good pair가 된다.그러므로, 특정 값 key = nums[i] - i를 기준으로 그룹을 만들고, 동일한 값이 등장할 때마다 good pair를 세면, 전체 쌍에서 빼서 bad pair를 구할 수 있다. 아래는 처음에 2중 for문으로 bruteforce로 풀었다가 time out 이 발생했던 코드..ㅠㅠ# solve 1)class Solution: def countBadPairs(self, nums: List.. 2025. 2. 9. [LeetCode] 2349. Design a Number Container System (Python) Problem Solutionhash change : 해당 index에 number를 저장하거나 이미 index에 Number 가 저장되어있으면 업데이트find: number에 대해서 어떤 인덱스에 존재하는지를 찾는다. number가 저장된 index 가 많으면 가장 최솟값 반환, 없으면 -1 반환 dict를 사용해야겠다고 생각했고 value 는 list로 구현해서 sorted 로 최솟값을 구해야겠다고 생각했다.그런데 SortedSet이 있는지 몰랐는데 이걸 사용하니 따로 sorted 를 안해주어도된다! 그리고 어떤 index 에 number 가 저장되어있는지 기록하는 변수 d,각 number 에 어떤 indicies들이 저장되어있는지 기록하는 변수 map 을 사용했다. Changechange 에서 ma.. 2025. 2. 8. [LeetCode] 3160. Find the Number of Distinct Colors Among the Balls (Python) Problem Solutionhashballs: x위치에 어떤 color 인지 저장count_colors: 특정 color 가 몇번 등장했는지 count 만약 x 위치의 공이 이미 색칠되어있다면, 해당 색상 - 1 Codeclass Solution: def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]: n = len(queries) balls = dict() count_colors = defaultdict(int) answer = [] cnt = 0 for i in range(n): x, color = queries[i] .. 2025. 2. 8. [LeetCode] 1726. Tuple with Same Product (Python) Problem Solutionpermutation순열과 조합을 사용하여 푸는 문제.defaultdict 의 value를 리스트로 선언하여 2개의 integer 곱을 key로, tuple 을 value로 저장하였다.value 길이 (리스트)가 2 이상이면 value 길이만큼 8 x nC2 를 곱하여 경우의 수를 구하고 정답에 ++ 하였다.8을 곱하는 이유는 a*b = c*d 인 (a,b,c,d)의 경우의 수가 8이기 때문! ( 4permutation * 2 pairs)nC2를 한 이유는 value 길이 = n 에서 2개의 튜플을 선택해야되기 때문! Codefrom collections import defaultdictclass Solution: def tupleSameProduct(self, nums.. 2025. 2. 7. [LeetCode] 1800. Maximum Ascending Subarray Sum (Python) ProblemSolutionsliding window이전 문제와 유사하게 sub array 중 오름차순이면서 총 원소합의 최대값을 구하는 문제.num array 가 100 이하라서 2중 포문을 사용해되지만 최대한 fot문을 1번만 사용하려고했다. 강력한 힌트는 The end of each ascending subarray will be the start of the nextsubarray 만들고 체크한 마지막 인덱스가 다음 순회 인덱스의 첫번째 인덱스가 된다. 아래 코드에서 idx 가 그 역할. 아래는 더 깔끔한 코드가있어서 가져와봤다.아예 처음부터 처음 0번째 값을 넣은 리스트를 선언 후 증가하는 값이 나올때마다 리스트에 추가 (cur list)작아지는 숫자가 나오면 max 값 구하고 다시 cur li.. 2025. 2. 4. 이전 1 2 3 4 5 다음 728x90
