Two Pointers

문제 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/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라는 결과를 얻을 수 있는데, 우리는 정확한 부분 수열의 형태보다 경우의 수만 알면 되기 때문이다. ...