문제 https://leetcode.com/problems/shift-2d-grid 풀이 $m \times n$ 2d 그리드에 있는 원소들을 오른쪽으로 k번 민 결과를 리턴하면 된다. grid[row][n - 1] → grid[row + 1][0] : 마지막 열의 원소는 다음 행의 첫 번째 열로 이동 grid[m - 1][n - 1] → grid[0][0] : 마지막 행의 마지막 열 원소는 첫 번째 행의 첫 번째 열로 이동 k번 직접 반복하는 대신, 그리드를 1차원으로 평탄화하면 shift 연산이 단순한 배열 회전으로 바뀐다. 평탄화한 배열을 오른쪽으로 k칸 회전시킨 뒤, 다시 $m \times n$ 2차원 배열로 복원하면 된다. 단, k가 배열 길이 $m \times n$ 보다 클 수 있으므로 모듈러 연산으로 정규화한다. ...
문제 https://leetcode.com/problems/smallest-subsequence-of-distinct-characters 풀이 문자열 s에 있는 모든 개별 문자를 정확히 한 번씩 포함하는 부분수열 중, 사전순으로 가장 작은 것을 리턴하면 된다. 처음에 투 포인터를 생각했는데, 원소가 굳이 쭉 이어질 필요가 없으니 스택을 활용했다. 처음에 전처리로 각 문자의 마지막 등장 인덱스를 구해둔다. 스택 top의 마지막 인덱스가 현재 인덱스보다 크면 뒤에 또 나온다는 뜻이므로 제거할 수 있다. 스택에 문자를 추가하기 전, 아래 세 조건을 모두 만족할 때 top을 pop하면 된다. 스택이 비어있지 않다 스택 top이 현재 문자보다 크다 (사전순으로 뒤에 있다) 스택 top 문자가 뒤에 또 등장한다 (lastIndice[stack[-1]] > idx) 코드 class Solution: def smallestSubsequence(self, s: str) -> str: stack = [] lastIndice = {} for idx, c in enumerate(s): lastIndice[c] = idx for idx, c in enumerate(s): if c in stack: continue while stack and c < stack[-1] and lastIndice[stack[-1]] > idx: stack.pop() stack.append(c) return "".join(stack)
문제 https://leetcode.com/problems/sum-of-gcd-of-formed-pairs 풀이 문제에서 지시한 내용을 그대로 구현하면 되는 문제다. 문제의 지시사항은 다음과 같다: 인티저 배열 nums의 누적 최대값 배열 mx를 만든다. prefixGcd[i] = gcd(nums[i], mx[i]) 으로 이루어진 배열을 만든다. prefixGcd를 오름차순 정렬한다. prefixGcd의 제일 큰 값과 제일 작은 값의 쌍을 만들어, GCD를 구하는 것을 더 이상 만들지 못할 때 까지 반복한다. 만약 prefixGcd의 원소의 개수가 홀수라서 페어을 만들지 못한 하나가 남는다면 무시한다. ‘4’에서 구한 모든 GCD 값의 합을 리턴한다. 페어을 만드는건 간단한 형태의 투 포인터로 해결했다. 정렬과 유클리드 호제법을 제외하곤 모두 $O(n)$에 해결되기 때문에, 시간복잡도는 $O(n \log n + n \log V) = O(n \log (nV))$이다. ...
문제 https://leetcode.com/problems/gcd-of-odd-and-even-sums 풀이 인티저 n이 하나 주어지고 작은 짝수 n개, 가장 홀수 n개를 각각 모두 더한 합 간의 GCD를 구하는 문제이다. 문제에서 요구하는 내용이 너무 간단해서, gcd()를 쓰지 않고, 유클리드 호제법을 직접 작성해서 GCD를 구했다. 코드 class Solution { public: int gcdOfOddEvenSums(int n) { int sumOdd = 0; int sumEven = 0; for (int num = 1; num <= n * 2; num++) { if (num % 2 == 0) sumEven += num; else if (num % 2 != 0) sumOdd += num; } while(sumEven) { sumOdd %= sumEven; swap(sumOdd, sumEven); } return sumOdd; } };
문제 https://leetcode.com/problems/find-the-number-of-subsequences-with-equal-gcd 풀이 수열 nums이 주어지고, nums에서 서로 원소가 겹치지 않게 부분 수열을 두 개 만든 뒤, 각 부분 수열(이하 A, B라 함)의 GCD가 같은 경우의 수를 찾는 문제이다. 만약 브루트 포스를 시도한다면, 원소의 개수 n, 각 원소가 가질 수 있는 상태가 3개(부분 수열 A, 부분 수열 B, 아예 미포함)이므로, 시간 복잡도가 $O(n \times 3^n)$ 이 되는데, nums의 최대 크기가 200이므로 유효한 시간 내에 해결할 수 없다. 하지만 부분 수열을 점점 채워나가면서 두 부분 수열을 비교할 수 있으므로, DP를 사용하면 O(n * 부분 수열A의 최대 gcd * 부분 수열B의 gcd 최대값)이 된다. 문제의 제약조건에서 원소의 최대 크기는 200이고, GCD는 원소보다 클 수 없으므로, $O(n \times 200 \times 200)$으로 줄일 수 있다. ...
문제 https://leetcode.com/problems/rank-transform-of-an-array 풀이 배열의 각 원소를 크기 기준으로 순위로 변환해 리턴하는 문제이다. 배열을 정렬한 뒤 각 원소에 순위를 매핑하고, 원본 배열 순서대로 순위를 꺼내 리턴한다. 문제에서 주의점이 하나 있는데, 같은 숫자는 같은 순위를 가진다는 것이다. 따라서 매핑할 때, 중복처리를 해줘야 한다. 코드 class Solution: def arrayRankTransform(self, arr: List[int]) -> List[int]: sortedArr = sorted(arr) rankDict = {} rank = 1 for element in sortedArr: if not element in rankDict: rankDict[element] = rank rank += 1 return list(map(lambda x: rankDict[x], arr))
문제 https://leetcode.com/problems/sequential-digits 풀이 low와 high 사이의 수 중, 각 자릿수가 123, 3456 처럼 연속으로 이어지는 수를 모두 리턴하는 문제이다 문제와 제약조건을 보고 바로 DFS 백트래킹로 풀어야겠다는 생각을 했다. 구간의 크기가 최대 1억이기 때문에, 하나하나 확인하는 것은 무리가 있다. 따라서 수를 하나씩 붙여나가면서 확인하고, 조건에 벗어나면 프룬닝 하면 되는 전형적인 문제로 생각했다. 백트래킹으로도 충분히 빠른 속도로 문제를 풀 수 있지만, 문제를 제출하고 난 뒤 효율성을 검증해보니. high 크기가 최대 1억이기 때문에, 후보들의 수가 몇개 되지 않기 때문에, 실제로 자리수가 연속되는 모든 숫자들을 만들고 확인하는 방식이 더 빠를수도 있다고 한다. ...
문제 https://leetcode.com/problems/path-existence-queries-in-a-graph-i 풀이 그래프 각 노드의 연결 조건이 주어지고, 들어오는 쿼리들에 있는 두 노드들이 연결되어있는지 확인하는 문제이다. queries 배열의 길이가 최대 10만이므로, BFS를 이용해서 풀기는 거의 불가능하다. BFS보다 더 빠르게 ‘연결 여부만’ 확인하는 방법은 Union-Find Set을 사용하면 된다. 우선 연결 조건은 두 노드의 절대 차이(노드 번호의 차이의 절대값)가 maxDiff 이하여야 하는데, 문제에서 nums 배열이 오름차순으로 정렬되어 있다고 했으므로, nums[j] - nums[i] <= maxDiff 를 만족하는 연속된 범위를 투 포인터로 찾을 수 있다. ...
문제 https://leetcode.com/problems/find-the-maximum-number-of-elements-in-subset/ 풀이 주어진 배열의 원소들로 만들 수 있는 가장 긴 [x, x², x⁴, ..., x^(2^k), ..., x⁴, x², x] 형태의 부분집합 길이를 반환하는 문제다. 이하에서는 이 형태를 피라미드라고 부른다. 어떤 문제든 제약 조건이 중요하지만, 이 문제는 특히 제약 조건이 중요하다. 주어진 꼴에서 원소들은 급격히 증가하는데, 1 <= nums[i] <= 10^9 라는 제약 조건이 있기에, 배열의 최대 크기를 예상할 수 있다. x가 1일 때는 몇 번을 제곱해도 1이므로, nums 배열 내부에 있는 1의 개수에 따라 달려있다. 피라미드 꼴은 항상 홀수이므로, 1의 개수가 홀수일때는 그대로, 짝수일때는 1을 뺀 값을 문제에서 요구하는 최대값의 초기 값으로 정한다. ...
문제 https://leetcode.com/problems/concatenate-non-zero-digits-and-multiply-by-sum-ii 풀이 1번 문제와 로직은 동일하다. 차이점은 스트링 s의 서브스트링에 같은 작업을 queries마다 반복해야 한다는 점이다. queries의 원소가 최대 10만 개이므로, 매 쿼리마다 부분 문자열을 슬라이싱해서 처리하면 시간 초과가 난다. 따라서 전처리를 통해 각 쿼리를 $O(1)$ 혹은 $O(n \log n)$에 처리할 수 있도록 해야 한다. 전처리 단계에서 네 가지 누적 배열을 만든다. pow10: $\text{pow10}[i] = 10^i \mod (10^9 + 7)$ preSum: 각 인덱스까지 자릿수의 합 preConcat: 각 인덱스까지 0이 아닌 숫자들을 이어붙인 값 nonZeroCount: 각 인덱스까지 0이 아닌 숫자의 개수 쿼리 [l, r]이 들어오면 네 배열로 x와 sum을 $O(1)$에 구해 $x \times \text{sum} \mod (10^9 + 7)$를 리턴한다. 0이 아닌 숫자가 없는 경우는 수식이 자연스럽게 $0$을 리턴하게 된다. ...