3. 투 포인터
2개의 포인터로 알고리즘의 시간 복잡도를 최적화하는 것.
006 숫자의 합 구하기(백준2018)
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.
예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.
N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 정수 N이 주어진다.
출력
입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오
예제 입력 1
15
예제 출력 1
4
문제 분석
1
- count = 1 : N 일때 해당 N만 뽑는 경우의 수
2
-
start_index : 오른쪽으로 한 칸 이동 = 왼쪽 값 삭제
-
end_index : 자연수의 범위를 한 칸 더 확장
-
같을 때는 경우의 수를 1 증가시키고 end_index 를 오른쪽으로 이동
-
sum > N : sum = sum - start_index; start-index++;
-
sum < N : end_index++; sum = sum + end_index;
-
sum == N: end_index++; sum = sum + end_index; count++;
3
- end_index 가 N 이 될 때까지 반복
- 포인터가 이동할 때마다 현재의 총 합과 N을 비교
값이 같으면 count++;
슈도코드
N 변수 저장
사용 변수 초기화
(count = 1, start_index = 1, end_index = 1, sum = 1)
while(end_index != N){
if(sum == N) count ++, end_index ++, sum 값 변경
else if(sum > N) sum 값 변경, start_index ++
else if(sum < N) end_index++, sum 값 변경
}코드
package cdTest;
import java.io.IOException;
import java.util.Scanner;
public class Test {
public static void main(String[] args) throws IOException{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int cnt = 1;
int si = 1;
int ei = 1;
int sum = 1;
while(ei != N) {
if(sum == N) {
cnt ++;
ei ++;
sum -= si;
} else if(sum > N) {
sum -= si;
si ++;
}else {
ei ++;
sum += ei;
}
}
System.out.println(cnt);
}
}
007 주몽의 명령(백준1940)
주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.
갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.
예제 입력 1
6 // 재료의 개수
9 // 갑옷이 완성되는 번호의 합
2 7 4 1 5 3 // 재료들
예제 출력 1
2
문제 분석
-
두 번호의 합, 크기 비교 문제 : 정렬
-
N 의 최대 범위 15,000 이므로 O(nlogn) 시간 복잡도 알고리즘 사용 ㅇㅋ
-
일반적으로 정렬 알고리즘의 시간복잡도는 O(nlogn)
-
N 개의 재료를 정렬 후 양쪽 끝의 위치를 투 포인터 지정
-
재료데이터 배열 A[N] 을 오름차순 정렬
-
투포인터 i, j 를 양쪽 끝에 위치 후 조건에 따라 탐색 수행
-
A[i] + A[j] > M: j--; // 번호의 합이 너보다 크므로 큰 번호 index--;
-
A[i] + A[j] < M: i++; // 번호의 합이 너보다 작으므로 작은 번호 index++;
-
A[i] + A[j] == M: i++； j--; count++; //양쪽 포인터를 모두 이동시키고 count++;
-
i와 j가 만날때 까지 반복
슈도코드
N(재료의 개수), M(갑옷이 되는 번호) 저장
for(N 반복){
재료 배열 저장
}
재료 배열 정렬
while(i<j){
if(재료 합 < M) 작은 번호 재료를 한 칸 위로 변경
else if(재료 합 > M) 큰 번호 재료를 한 칸 아래로 변경
else 경우의 수 증가, 양쪽 index 각각 변경
}
count 출력코드
package cdTest;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Test {
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int M = Integer.parseInt(bf.readLine());
int[] A = new int[N];
StringTokenizer st = new StringTokenizer(bf.readLine());
for(int i=0; i<N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(A);
int cnt = 0;
int i = 0;
int j = N-1;
while(i<j) {
if(A[i] + A[j] < M) {
i++;
}else if(A[i] + A[j] > M) {
j++;
}else {
cnt ++;
i++;
j--;
}
}
System.out.println(cnt);
bf.close();
}
}008 '좋은 수' 구하기(백준1253)
제한
시간 : 2초 / 메모리 : 256 MB
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.
입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
출력
좋은 수의 개수를 첫 번째 줄에 출력한다.
예제 입력 1
10
1 2 3 4 5 6 7 8 9 10
예제 출력 1
8
힌트
3,4,5,6,7,8,9,10은 좋다.
문제 분석
- 시간복잡도 : N 최대 2,000
- 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2 보다 작아야 한다.
- 만약 N^2인 알고리즘을 사용하면 최종 시간 복잡도는 N^3이 되어 제한 시간 안에 문제를 풀 수 없다.
- 따라서 시간복잡도는 최소 O(nlogn)이어야 한다.
- 결론 : 투 포인터 알고리즘 사용
손으로 풀어보기
-
수를 입력받아 배열에 저장 후 정렬
-
투 포인터 i, j 를 배열 A 양쪽 끝에 위치시키고 조건에 적합한 투 포인터 이동 원칙 활용하여 탐색
-> 판별의 대상이 되는 수는 K 라고 가정투 포인터 이동 원칙
- A[i] + A[j] > K: j--; A[i] + A[j] < K: i++;
- A[i] + A[j] == K: i++; j--; count++;
슈도코드
N（수의 개수）
A（수 데이터 저장 배열）
for（N만큼 반복하기）{
A 배열에 데이터 저장하기
}
A 배열 정렬하기
for（k를 0부터 N까지 반복）{
변수 초기화하기（찾고자 하는 값 find, 포인터 i, 포인터 j）
wtiile（i < j）{
if（A[i] + A[j] == 찾고자 하는 값）
두 포인터 i, j가 k가 아닐 때 결괏값에 반영 및 while 문 종료하기
두 포인터 i, j가 k가 맞율 때 포인터 변경 및 계속 수행하기
else if（A[i] + A[j] < 찾고자 하는 값) 포인터 i 증가
else 포인터 j 감소
}
}
좋온 수의 개수 출력하기코드
package cdTest;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Test {
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int result = 0;
long[] A = new long[N];
StringTokenizer st = new StringTokenizer(bf.readLine());
for(int i=0; i<N; i++) {
A[i] = Long.parseLong(st.nextToken());
}
Arrays.sort(A);
for(int k=0; k<N; k++) {
long find = A[k];
int i = 0;
int j = N-1;
// 투 포인터 알고리즘
while(i<j) {
if(A[i] + A[j] == find) {
// find 는 서로 다른 수의 합이어야 함을 체크
if( i!=k && j!=k) {
result ++;
break;
}else if(i == k) {
i ++;
}else if(j == k) {
j --;
}
}else if(A[i] + A[k] < find) {
i++;
}else {
j--;
}// if else if ;
}// while ;
} // for ;
System.out.println(result);
bf.close();
}
}
