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..

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 ..

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..

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:..

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..

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(): ..