728x90 코딩 테스트101 [LeetCode] 3191. Minimum Operations to Make Binary Array Elements Equal to One I (Python) Problem Solutionsliding window 연속된 3개 숫자를 뒤집어서 모두 1로 바꿀 수 있는 최소한의 횟수를 구하는 문제.당연히 2중포문을 쓰면 시간초과가 발생한다.n-2까지만 검사해서 nums[i] == 0 이면 i ~ i+2까지 비트연산으로 1, 0을 뒤집는다.연산이 끝나면 answer+=1비트연산 파이선으로 ^= 이더라? 괜히 if~else 구문으로 바꾸고있었네 마지막에 2개숫자가 0이면 연속된 3자리가 아니라 못바꾸므로 바로 리턴 -1아니면 answer return Codeclass Solution: def minOperations(self, nums: List[int]) -> int: n = len(nums) ans = 0 for i i.. 2025. 3. 19. [LeetCode] 3208. Alternating Groups II (Python) Problem Solutionsliding window 처음에 구현으로 2중 포문 돌렸다가 time limit exceeded 났던 문제.이 문제도 똑같이 sliding window 기법으로 풀어야된다.원형 배열이라서 colors[: k-1]개만큼 기존 배열에 더해준다.그리고 이전 원소와 값을 비교하며 (index 범위는 1 부터 시작) count 를 증가한다.count가 k 이상이면 조건을 만족하므로 answer ++만족하지않으면 count = 1 로 초기화하여 다시 리셋해준다. Codeclass Solution: def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int: n = len(colors) .. 2025. 3. 9. [LeetCode] 2379. Minimum Recolors to Get K Consecutive Black Blocks (Python) ProblemSolutionstringsliding window blocks string에서 연속된 B의 개수가 k개가 될 수 있도록 가장 최소한의 변경해야되는 W 수를 구하는 문제.substring에서 힌트를 얻어서 k길이만큼 substring을 구하고 W의 개수를 구한뒤 가장 최소값을 리턴하였다. 나는 구현으로 일일이 string을 검사하는 방식으로 풀이했는데 슬라이딩 윈도우 기법을 사용하면 더 최적화된 알고리즘 O(N)으로 해결할 수 있다. Codeclass Solution: def minimumRecolors(self, blocks: str, k: int) -> int: n = len(blocks) answer = 999 if 'W' in blocks a.. 2025. 3. 8. [LeetCode] 2965. Find Missing and Repeated Values (Python) Problem Solutionarrayn*n 2차 배열에서 중복된 값, 존재하지 않는 값을 찾는 문제.hash를 사용해서 frequency를 구한다음에 정답을 구해도되고나는 1~n*n까지 연속된 숫자이므로 visited 를 사용해서 이미 방문했는지를 체크하도록 했다. Codeclass Solution: def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]: answer = [] n = len(grid) visited = [0] * (n*n + 1) twice_num = 0 missing_num = 0 for i in range(.. 2025. 3. 6. [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. 이전 1 2 3 4 ··· 6 다음 728x90
