본문 바로가기

투포인터11

[leetcode][719] Find K-th Smallest Pair Distance 문제 : https://leetcode.com/problems/find-k-th-smallest-pair-distance/ 모든 요소들의 pair들의 최소 차 중 k 번째가 되는 수를 구하는 문제. 이진탐색으로 정답이 되는 범위를 줄여나가면서 찾는다. 여기서 low, high, mid는 단순히 nums 배열의 인덱스가 아닌 pair의 차이가 된다. 즉, low = 정답이 가능한 범위의 pair 최소 차이 high = 정답 범위의 pair 최대 차이 mid = 범위를 줄이기 위해 몇 번째 최소 차인지 비교하기 위한 수. 가 된다. nums를 오름차순으로 정렬한다. low = 0, high = 최대값 - 최소값으로 세팅한다. low를 nums를 한 번 탐색하면서 nums[i+1] - nums[i] 중 최소값.. 2019. 12. 21.
[leetcode][1021] Best Sightseeing Pair 문제 : https://leetcode.com/problems/best-sightseeing-pair/ 투포인터로 풀었다. 배열 A를 1 인덱스부터 탐색하면서 탐색 중인 원소를 j 인덱스로 본다. A[i] + A[j] + i - j의 최대값이 정답이다. i 인덱스는 A[i] 2019. 3. 29.
[leetcode][1004] Max Consecutive Ones III 문제 : https://leetcode.com/problems/max-consecutive-ones-iii/ 투 포인터로 풀었다.큐를 하나 만들어서 0인 경우 0일 때의 인덱스를 큐에 저장한다.그리고 start, end 인덱스 2개를 저장한다. A 배열을 앞에서 탐색하면서 탐색 중인 인덱스가 end인덱스가 되는 정답이 될 수 있는 가능한 start 인덱스를 갱신해나간다.start인덱스는 0부터 시작되며 갱신되는 경우는 [start, end] 범위에 0의 개수(0 인덱스를 저장하는 큐의 size)가 K개를 초과하는 경우이다.start는 큐의 가장 앞에 있는 0의 인덱스 + 1이 된다.A 배열을 모두 탐색하면서 가능한 [start, end] 범위를 구하고 해당 범위의 길이 중 최대 값이 정답이 된다.시간복잡.. 2019. 3. 4.
[BOJ][2003] 수들의 합 2 문제 : https://www.acmicpc.net/problem/2003 부분합 + 투포인터 로 풀었다. N개의 수를 입력받으면서 부분합 배열을 만든다.subSum[i] = i까지 수들의 합. 인덱스 변수 2개를 준비한다. (l, r)2개의 변수는 부분합의 범위를 구하는데 사용되며 범위는 (l, r] 이다.범위가 (l, r] 일 때 해당 부분 배열의 합은 subSum[r] - subSum[l] 이 된다. l, r을 0에서부터 증가시키면서 해당 부분 배열의 합이 M과 같다면 정답이 될 수 있는 경우이다.합이 M보다 작다면 부분 배열의 합이 더 커져야 하므로 r을 증가시키고M보다 크다면 합이 더 작아져야 하므로 l을 증가시킨다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com.. 2019. 2. 16.
[leetcode][992] Subarrays with K Different Integers 문제 : https://leetcode.com/problems/subarrays-with-k-different-integers/ 투포인터로 풀었다.A = 2212211이고 K가 2일 때를 예로 들어보자.인덱스 r이 1일 때,인덱스 l은 K가 2일때를 만족하는 인덱스 0부터 시작한다.이 때, 인덱스 r을 포함시키는 정답이 될 수 있는 경우의 수를 구한다.인덱스 0부터 A[i]의 개수가 1개일 때까지 l을 증가시킨다.정답이 될 수 있는 경우는 이 때 인덱스 l의 증가량 +1이 된다. 정답이 될 수 있으려면 최소한 1개의 범위 내에 각 숫자를 최소한 한 개는 가지고 있어야 한다.즉, 인덱스 r을 포함한 정답가능한 최소 문자열은 위 그림과 같이 "2 1" 이다.여기에서 K가 2일 때를 만족하는 범위의 인덱스들을.. 2019. 2. 14.