📢 1) 투 포인터
(1) 개념
시작 인덱스와 종료 인덱스 지정
- 시작 인덱스를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 '삭제'하는 것
- 종료 인덱스를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한칸 더 확장하는 것
- 같을 때는 경우의 수 1 증가 시키고 종료 인덱스 오른쪽 이동
(2) 이동 원칙
- sum > N : sum = sum - start_index; start_index++;
- sum < N : sum = sum + end_index; end_index++;
- sum == N : end_index++; sum = sum + end_index; count++;
문제 1. 백준 2018번 연속된 자연수의 합 구하기
🔎 접근법
: N의 최대값이 10,000,000이므로 O(n) 복잡도 알고리즘 사용
- 연속된 자연수 합 구하는 것이기 때문에 시작인덱스와 끝 인덱스 지정
1. sum이 n보다 작을 때:
- end_index를 증가시키고 증가된 end_index 값을 sum에 추가한다.
- end_index는 연속된 자연수를 더해주는 역할이기 때문에 현재 값(end_index)을 먼저 더한 후 증가한다.
2. sum이 n보다 클 때:
- start_index를 먼저 sum에서 빼고 나서 start_index를 증가시킨다.
- start_index는 더 이상 필요 없는 구간을 제거하는 역할을 하기 때문에 현재 값(start_index)을 빼고 나서 증가한다.
import java.util.Scanner;
class Main {
public static void main(String[] args) {
/* 백준 2018번 연속된 자연수의 합 구하기 */
Scanner sc = new Scanner(System.in);
// 1) 값 초기화
int n = sc.nextInt();
int count = 1; // n 자체를 선택할 경우 카운트
int sum = 1;
int start_index = 1;
int end_index = 1;
// 2) 계산
while(end_index != n) {
if(sum > n) { // 합이 정해진 수보다 클 경우 (빼준다-> start 움직이기)
sum -= start_index;
start_index++;
}
else if (sum < n) { // 합이 정해진 수보다 작을 경우 (더해준다 -> end 움직이기)
end_index++;
sum += end_index;
}
else { // 합이 N과 같을 경우 (count 횟수 올린다 후에 end 움직이기)
count++;
end_index++;
sum += end_index;
}
}
System.out.println(count);
}
}
문제 2. 백준 1940번 주몽의 명령
🔎 접근법
- 위에랑 비슷한 문제긴 하지만 연속된 자연수가 아니고 입력받은 숫자 내의 합을 구해야 함으로 투 포인터를 사용하기 위해 정렬을 먼저 해 줘야 한다.
- 같은 지점이 아닌 정렬의 시작과 끝에 위치
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
/* 백준 1940번 주몽의 명령 */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1) 값 초기화
int n = Integer.parseInt(br.readLine());
int sum = Integer.parseInt(br.readLine());
int [] in = new int[n];
StringTokenizer line = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
in[i] = Integer.parseInt(line.nextToken());
}
// 정렬
Arrays.sort(in);
int count = 0; // 횟수
int start = 0; // 시작 포인터
int end = n-1; // 끝 포인터
// 2) 계산
while (start < end) { // 교차 시 중지
int nSum = in[start] + in[end];
if(nSum > sum) end--; // 정해진 합보다 클 경우 end 포인터 감소
else if (nSum < sum) start++; // 정해진 합보다 작을 경우 start 증가
else {
count++;
end--;
start++;
}
}
System.out.println(count);
}
}
문제 3. 백준 1253번 좋은 수 구하기
🔎 접근법
- 정렬할 것
- 같은 지점에서 시작할 것인지 / 양쪽 끝과 끝에서 시작할 것인지
==> 양쪽 끝에서 시작 - 두 수의 합이 배열 안에 존재함을 판별해야 함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws IOException {
/* 백준 1253번 좋은 수 구하기 */
// 1. 변수 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer line = new StringTokenizer(br.readLine());
int [] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(line.nextToken());
}
int count = 0;
// 2. 정렬
Arrays.sort(nums);
// 3. 계산
for(int i = 0; i < n; i++) {
int start = 0; // 값을 찾기 위해서 다시 처음부터 시작해야 하니 while문 밖에 선언
int end = n-1;
int find = nums[i]; // 찾을 값
while(start < end) {
if (start == i) {
start++;
continue;
}
if (end == i) {
end--;
continue;
}
int nSum = nums[start] + nums[end];
if (nSum == find) {
count++;
break; // 좋은 수를 찾았으니 다음 i로 넘어감
} else if (nSum < find) {
start++;
} else {
end--;
}
}
}
System.out.println(count);
}
}
~*