Problem Solving

문제 https://leetcode.com/problems/stone-game-v 풀이 돌이 일렬로 놓여 있고, 매 턴마다 현재 구간을 둘로 나눈 뒤 더 작은 합을 가진 쪽을 가져간다. Alice가 얻을 수 있는 최대 점수를 리턴하는 문제이다. 매 턴마다 현재 구간을 둘로 나눈 뒤 더 작은 합을 가진 쪽을 가져가므로, 구간 DP로 보는 게 자연스럽다. dp[left][right]를 stoneValue[left...right] 구간에서 Alice가 얻을 수 있는 최대 점수라고 하자. 구간을 split으로 나눠서 왼쪽 합과 오른쪽 합을 비교하면 된다. 왼쪽 합이 더 작으면 왼쪽을 가져간다. 오른쪽 합이 더 작으면 오른쪽을 가져간다. 두 합이 같으면 둘 중 더 좋은 쪽을 선택한다. 구간 합은 Prefix Sum으로 미리 구해두면 되고, dp는 짧은 구간부터 채우면 된다. 각 구간마다 모든 분할을 확인하므로 전체 시간 복잡도는 $O(n^3)$이다. ...

문제 https://codeforces.com/problemset/problem/1360/D 풀이 정확히 n개의 삽을 사야 하고, 한 번에 살 수 있는 패키지 크기는 1부터 k까지이다. 또한 한 번 고른 패키지 크기만 계속 사야 하므로, 결국 n을 나누는 어떤 수 x를 골라 n / x개의 패키지를 사는 문제로 바뀐다. 패키지 개수를 최소화하려면 패키지 크기 x를 최대한 크게 잡아야 한다. 따라서 n의 약수 중에서 k 이하인 가장 큰 값을 찾으면 된다. 예를 들어 n = 8, k = 7이면 8의 약수는 1, 2, 4, 8인데, 이 중 k 이하인 가장 큰 약수는 4이다. 그래서 답은 8 / 4 = 2가 된다. ...

문제 https://leetcode.com/problems/stone-game-ix 풀이 돌을 순서대로 가져가면서, 합이 3의 배수가 되지 않게 해야 하는 게임이다. Alice가 이길 수 있는지 리턴하는 문제이다. 각 돌의 값은 3으로 나눈 나머지만 보면 된다. 합이 3의 배수인지 아닌지만 중요하기 때문이다. 그래서 0, 1, 2의 개수만 세면 충분하다. 0은 합의 나머지를 바꾸지 않으므로, 실제 승부는 1과 2를 어떻게 번갈아 쓰느냐에 달려 있다. count[0]이 짝수인지 홀수인지에 따라 가능한 진행이 달라진다. count[0]이 짝수면 1과 2가 둘 다 있어야 한다. count[0]이 홀수면 1과 2의 개수 차이가 너무 크면 안 된다. 코드 class Solution { func stoneGameIX(_ stones: [Int]) -> Bool { var count = [Int](repeating: 0, count: 3) for stone in stones { count[stone % 3] += 1 } let count0 = count[0] let count1 = count[1] let count2 = count[2] if count0 % 2 == 0 { return count1 > 0 && count2 > 0 } return abs(count1 - count2) > 2 } }

문제 https://codeforces.com/problemset/problem/276/C 풀이 크기 n인 수열 a와 쿼리 q개가 주어진다. 각 쿼리는 인덱스 $[l, r]$ 범위를 지정하며, 해당 범위의 원소 합을 구한다. 수열 a를 적절히 재배열하여 모든 쿼리의 합의 총합을 최대화 한 수를 출력하면 된다. 쿼리가 여러번 나오고 어떤 원소들은 쿼리 안에 중복되어서 포함되어 있을 수 있다. 쿼리의 범위 안에 가장 많이 포함된 원소의 순서대로, 높은 값을 배치하는 정렬 문제로 환원된다. 어떤 원소 $a_i$가 쿼리 내부에 포함되어 있는지를 일반적으로 판단하게 되면 $O(q \times n)$이 되는데, q, n의 범위가 $1 \leq q 2 \times 10^5$ 이므로, 시간 안에 문제를 해결하기 어려워진다. ...

문제 https://leetcode.com/problems/longest-subsequence-with-non-zero-bitwise-xor 풀이 수열 nums가 주어지고, 이 nums의 서브시퀀스 중, 모든 원소를 XOR해서 0이 아니게 되는 서브시퀀스의 최대 길이를 리턴하면 된다. 이 문제는 XOR 연산의 특성을 잘 알아야 한다. 만약 XOR이 아니라 $+$이었다면, 모든 $\text{nums}$의 원소들을 더해보고, 0이 아니라면 $\text{nums}$ 전체를, 0이라면 원소 중 0이 아닌 것 하나를 제외하면 된다. $+$의 역연산은 $-$이므로, 어떤 원소 $x$를 제외했을 때 다음과 같이 된다. $$\sum \text{nums} - x \neq 0$$ 만약 모든 원소가 0이라면 답은 0이 된다. ...

문제 https://codeforces.com/problemset/problem/550/A 풀이 스트링 s가 주어지고, 이 s 안에서 서브스트링 "AB"와 "BA"가 겹쳐지지 않은 상태로 존재하면 "YES" 아니라면 "NO" 출력하면 된다. 문제에서 주어진 예시인 "ABA" 같은 경우는 "NO"가 된다. "AB"와 "BA"가 서로 따로 존재하지 않기 때문이다. 하지만 "ABCABA" 같은 경우에는 "AB"와 "BA"가 "BA"는 겹쳐져 있지만 이미 앞에서 "AB"가 존재하기 때문에, "YES"가 된다. 이런 예외들을 알아내면, 문제를 푸는 방식은 단순하다. "AB"를 찾은 후, 그 이후("B" 이후)에 있는 인덱스부터 "BA"를 찾고, 만약 존재한다면 "YES", 존재하지 않는다면 다시 "BA"를 먼저 찾은 후, "A"의 인덱스 이후에 있는 인덱스부터 "AB"를 찾으면 된다. 둘 다 불가능하다면 "NO"가 된다. ...

문제 https://leetcode.com/problems/maximum-length-substring-with-two-occurrences 풀이 스트링 s가 주어지고, 스트링 s의 서브스트링 중에서 같은 문자가 최대 2번 까지만 등장하는 서브스트링의 최대 길이를 리턴하는 문제이다. 투 포인터를 이용해서, 서브스트링 내부의 각 문자의 개수는 frequencies 딕셔너리로 추적하고, 같은 문자가 2개를 초과하면 start, 그렇지 않다면 end를 증가시키는 방향으로 s를 탐색하면 된다. 문제의 제약조건이 널널해서 $O(n^2)$ 방식의 브루트 포스로도 풀 수 있지만 투 포인터를 이용하면 $O(n)$으로 쉽게 풀 수 있다. 코드 class Solution: def maximumLengthSubstring(self, s: str) -> int: frequencies = {} answer = 0 start = 0 for end in range(len(s)): frequencies[s[end]] = frequencies.get(s[end], 0) + 1 while frequencies[s[end]] > 2: frequencies[s[start]] -= 1 start += 1 answer = max(answer, end - start + 1) return answer

문제 https://leetcode.com/problems/longest-substring-of-one-repeating-character 풀이 스트링 s에 대해 여러 번의 문자 변경 쿼리가 주어진다. 각 쿼리마다 특정 인덱스의 문자를 변경하고, 같은 문자가 연속되는 가장 긴 부분 스트링의 길이를 리턴하면 된다. 스트링의 길이와 쿼리의 개수가 최대 $10^5$이므로, 문자를 변경할 때마다 스트링 전체를 탐색하는 방식으로는 해결할 수 없다. 문자 하나를 변경하는 업데이트가 반복되고, 변경 이후 스트링 전체에서 가장 긴 연속 스트링의 길이를 구해야 한다. 따라서 변경된 구간만 갱신할 수 있는 Segment Tree를 사용했다. 다만, 단순히 concat을 하면 안되고, 두 접합부의 경계를 확인한 다음 처리를 해줘야 한다. ...

문제 https://leetcode.com/problems/smallest-missing-integer-greater-than-sequential-prefix-sum 풀이 정수 배열 nums가 주어진다. 배열의 첫 원소부터 연속해서 증가하는 부분의 합을 구한 뒤, 그 합보다 크거나 같으면서 배열에 존재하지 않는 가장 작은 정수를 찾으면 된다. 먼저 첫 번째 원소를 합에 더해두고, 현재 원소가 다음 조건을 만족하는지 확인한다. $$ nums[i] = nums[i - 1] + 1 $$ 조건을 만족하는 동안에는 현재 원소를 합에 더하고, 연속 조건이 깨지면 순회를 종료한다. 이제 구한 합을 후보값으로 두고, 후보값이 배열 안에 있으면 1씩 증가시킨다. 배열에 없는 첫 번째 값이 정답이다. 이 부분은 코드처럼 배열에 후보값이 존재하는 동안 반복하면 된다. ...

문제 https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency 풀이 정수 배열 nums와 정수 k가 주어질 때, 어떤 숫자도 k번보다 많이 등장하지 않는 가장 긴 연속 부분 배열의 길이를 구하면 된다. 연속 부분 배열이므로 슬라이딩 윈도우를 사용했다. start부터 end까지를 현재 윈도우로 두고, end를 오른쪽으로 이동하면서 숫자별 등장 횟수를 갱신한다. 새로 추가한 숫자의 등장 횟수가 k를 초과하면 조건을 만족할 때까지 start를 오른쪽으로 이동한다. 이때 윈도우의 가장 왼쪽 숫자부터 하나씩 제거하면 된다. 윈도우가 조건을 만족하는 상태가 되면 현재 길이로 정답을 갱신한다. ...