Two Pointers

오늘 한 내용 LeetCode 2958. Length of Longest Subarray With at Most K Frequency LeetCode 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum StackDay. 엔티티와 계산 책임 분리하기 배운 내용 파생 값을 구현할 때의 책임 분리 StackDay의 HabitEntry와 HabitStreak을 구현했다. 모델링 단계에서 정의한 파생 값을 실제 코드로 옮기면서, 값을 표현하는 타입과 값을 계산하는 로직을 분리했다. AI 에이전트가 작성한 내용중에 별로인 것들을 몇개 직접 수정했는데 리스트로 정리하면 다음과 같다. HabitEntry의 이니셜라이저 전체 Completion 목록을 직접 탐색하고, 생성 실패/성공을 판정했다. HabitStreak의 이니셜라이저 내부에 Streak 계산 로직이 들어있었다. 둘 다 경계가 제대로 구분되지 않았다. HabitEntry 내부에서 전체 Completion을 탐색하면서 조건에 맞는 Completion을 찾아내는건 비효율적이기도 하고, 이건 유즈케이스에서 해야 될 일이다. ...

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

문제 https://codeforces.com/problemset/problem/451/B 풀이 n 크기 수열 a가 주어진다. 이 수열의 특정 구간을 선택해서 뒤집는 것을 1번 했을 때, 이 수열이 오름차순으로 정렬되어 있다면 "yes"와 그 구간을, 불가능하면 "no"를 출력하면 된다. n의 제약 조건이 $1 <= n <= 10^5$ 이기 때문에, 브루트 포스로는 시간 내에 풀기 힘들다. 특정 구간을 선택해서 뒤집는 행동을 1번만 한다는 것이 힌트인데, 구간 하나를 1번 뒤집어서 수열 전체가 오름차순이 된다는 것은, 수열의 일부 구간만 내림차순 이라는 것이다. ...

문제 https://codeforces.com/problemset/problem/279/B 풀이 책을 읽는데 걸리는 시간이 담긴 크기 n 배열 a가 주어지고, 책을 읽을 수 있는 시간 t가 주어진다. 특정 인덱스를 정해서 그 인덱스부터 책을 순서대로 읽었을때, 최대로 읽을 수 있는 책의 개수를 출력하면된다. 모든 경우의 수를 탐색하려면 $O(n^2)$의 시간 복잡도를 가지는데 책의 개수가 10만개 이므로, 시간 내로 해결하기는 힘들다. ‘순서대로’라는 조건이 있으므로, 투 포인터를 이용하면 쉽게 풀 수 있다. 단 배열 a의 원소의 크기가 t보다 클 수 있으므로, 단 한권의 책도 읽지 못하는 경우가 있다. 그래서 책을 0권 읽는 경우의 수도 생각해서 코드를 짜야 한다. ...

문제 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://www.acmicpc.net/problem/13144 풀이 매우 특이한 유형의 투 포인터 문제다. start, end가 증가만 해서는 모든 경우의 수를 나타낼 수 없으며, 모든 경우의 수를 탐색하려면 O(n^2)이 된다. 1 2 3 1 2 라는 수열이 있을 때를 생각해보자 겹치는 원소가 나오지 않도록 작성한 일반적인 투 포인터는 1, 12, 123, 231, 312 이렇게 5번 탐색을 하고 종료한다. 하지만 1 2 3 1 2의 정답은 5가 아니라 15이다. 하지만 이 5번의 탐색만으로도 15라는 결과를 얻을 수 있는데, 우리는 정확한 부분 수열의 형태보다 경우의 수만 알면 되기 때문이다. ...