[알고리즘] 02-3. 투 포인터

728x90

1. 투 포인터

: 2개의 포인터로 구하는 알고리즘

-> end_index가 끝에 도달할 때까지 반복

문제 06. 연속된 자연수의 합 구하기

어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(l <= N <= 10,000,000)을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶다. 이때 사용하는 자연수는 N이어야 한다. 예를 들어 15를 나타내는 방법은 15,7 + 8, 4 + 5 + 6,1 + 2+ 3 + 4 + 5이다. 반면，10을 나타내는 방법은 10,1 + 2 + 3 + 4이다. N을 입력받아 연속된 자연수의 합으로 나타내는 가짓수를 출력하는 프로그램을 작성하시오.

입력
1 번째 줄에 정수 N이 주어진다.

출력
입력된 자연수 N을 연속된 자연수의 합으로 나타내는 가짓수를 출력한다.

예제 입력 1

15 // N

예제 출력 1

1단계. 문제 분석하기

: 알고리즘의 범위를 줄여야 한다. -> 시간제한이 존재하는데, N의 최댓값이 10,000,000으로 매우 크기 때문이다

: O(nlogn)을 사용하면, 제한 시간을 초과하므로, O(n)의 시간 복잡도를 사용해야 한다.

-> 투 포인트 알고리즘을 사용해 시작 인덱스와 종료 인덱스를 지정해 연속된 수를 표현한다.

2단계. 손으로 풀어보기

입력받은 값을 N에 저장한 후 코드에서 사용할 변수를 모두 초기화
-> count를 1로 초기화할 경우 N이 결괏값과 같은 경우를 미리 넣은 걸로 가정
포인터를 이동시키면서, 배열을 끝까지 탐색하고 합이 N이 될경우를 구한다.

#투 포인터 이동 원칙
sum > N : sum = sum - start_index; start_index++;
sum < N : sum = end_index++; sum = sum + end_index++;
sum == N : end_index++; sum = sum + end_index; count++;
end_index가 N이 될 때까지 반복하면서, 포인터 이동할때마다 총합과 N을 비교해 같으면 count++;

3단계. 슈도코드 작성하기

N 변수 저장
사용 변수 초기화(count = 1, start_index = 1, end_index = 1, sum = 1) 
while(en in ex != N) {
    if(sum == N) count 증가, en in ex 증가, sum값 변경
    else if(sum N) sum값 변경, start index 증가
    else if(sum < N) end_index 증가, sum값 변경
}
count 출력하기

package datastructure.ch03;

import java.util.Scanner;

public class ds_q06_sol {
	public int solution(int n) {
		int answer=1;
		//n이 본인 n으로 되는 경우 미리 세기
		int sum=1;
		
		int p1=1;
		int p2=1;
		//종료조건
		
		
		//투 포인터 공식
		while(p2 !=n) {
			if(sum==n) {
//				(1) sum에서 p1을 빼는 방법
				answer++;
				sum-=p1;
				p1++;
				
//				(2) sum에서 p2를 추가하는 방법
//				answer++;
//				p2++;
//				sum+=p2;
			}
			else if(sum>n) {
				sum-=p1;
				p1++;
			}
			else {
				p2++;
				sum+=p2;
			}
		}
		

		return answer;
	}

	public static void main(String[] args) {
		ds_q06_sol T = new ds_q06_sol();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		System.out.println(T.solution(n));
	}
}

문제 07. 주몽의 명령

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장에게 철기군이 입을 갑옷을 만들라고 명령했다. 야철대장은 주몽의 명령에 따르기 위해 연구에 착수하던 중 갑옷을 만드는 재료들은 각각 고유한 번호가 있고, 갑옷은 2개의 재료로 만드는 데 2가지 재료의 고유한 번호를 합쳐 M(l < M < 10,000,000)이 되면 갑옷이 만들어진다는 사실을 발견했다.

야철대장은 자신이 만들고 있는 재료로 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 야철대장의 궁금증을풀어 주기 위해 N(1 <= N <= 15,000)개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력
1 번째 줄에 재료의 개수 N(1 <= N <= 15,000), 2번째 줄에 갑옷을 만드는 데 필요한 수 M(1 <= M <=10,000,000)01 주어진다. 3번째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수다.

출력
1 번째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

예제 입력 1

6 // 재료의 개수
9 // 갑옷이 완성되는 번호의 합
2 7 4 1 5 3 // 재료들

예제 출력 1

1단계. 문제 분석하기

: 두 재료의 번호의 합을 이용하는데, 재료의 순서가 정해지지 않았으므로, 정렬을 이용한다.

-> N의 범위가 15,000이므로 O(nlogn) 시간복잡도를 사용해도 됨

-> N개의 재룟값을 정렬 후, 양쪽 끝을 투 포인터로 지정해 접근

2단계. 손으로 풀어 보기

재료 데이터를 배열 arr[n]에 저장 후 오름차순 정렬
투 포인터 i,j를 양쪽 끝으로 지정 후, 문제의 조건에 맞게 포인터를 이동시켜 탐색
# 투 포인터 이동 원칙
arr[i] + arr[j] > M : j--;
arr[i] + arr[j] < M : i++;
arr[i] + arr[j] == M : i++; j--; count++;
종료 조건 : i와 j가 만날 때까지

3단계. 슈도코드 작성하기

N（재료의 개수）, M（갑옷이 되는 번호） 저장하기
for（N만큼 반복）
{
	재료 배열 저장하기
}
재료 배열 정렬하기
while（i < j）
{
    if（재료 합〈 M） 작은 번호 재료를 한 칸 위로 변경하기
    else if（재료 합〉M） 큰 번호 재료를 한 칸 아래로 변경하기
    else 경우의 수 증가, 양쪽 index 각각 변경하기
}
count 출력하기

package datastructure.ch03;

import java.util.Arrays;
import java.util.Scanner;

public class ds_q07 {
	public int solution(int m, int[] arr) {
		int answer = 0;
		int p1 = 0;
		int p2 = arr.length-1;
		
		Arrays.sort(arr);
		int sum=arr[p1]+arr[p2];
		// 두 재료의 합이 m이 되어야 하는데, 순서가 정해져 있지 않으므로,
		// 정렬이 필요함

		// 종료조건
		// -> start_index와 end_index가 만나야 종료
		// 오름차순이기 때문에, sum=arr[p1]+arr[p2]의 크기에 따라 증감

		// sum>m -> sum-=arr[p2]; p2--;
		// sum<m -> sum+=arr[p2]; p2--;

		while (p1<p2) {
			if (sum== m) {
				answer++;
				p2=arr.length-1;
				p1++;
				sum=arr[p1]+arr[p2];
			} else if (sum > m) {
				sum-=arr[p2];
				p2--;
				sum+=arr[p2];
			} else {
				sum-=arr[p1];
				p1++;
				sum+=arr[p1];
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		ds_q07 T = new ds_q07();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();

		System.out.println(T.solution(m, arr));
	}

}

+) 세련된 풀이

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public int solution(int m, int[] arr) {
		int answer = 0;
		int p1 = 0;
		int p2 = arr.length-1;
		
		Arrays.sort(arr);
		// 두 재료의 합이 m이 되어야 하는데, 순서가 정해져 있지 않으므로,
		// 정렬이 필요함

		// 종료조건
		// -> start_index와 end_index가 만나야 종료
		// 오름차순이기 때문에, sum=arr[p1]+arr[p2]의 크기에 따라 증감

		// sum>m -> sum-=arr[p2]; p2--;
		// sum<m -> sum+=arr[p2]; p2--;

		while (p1<p2) {
			int sum=arr[p1]+arr[p2];
			if (sum== m) {
				answer++;
				p1++;
				p2--;
			} else if (sum > m) {
				p2--;
			} else {
				p1++;
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();

		System.out.println(T.solution(m, arr));
	}

}

문제 08. '좋은 수' 구하기

주어진 N개의 수에서 다른 두 수의 합으로 표현되는 수가 있다면 그 수를 ‘좋은 수’ 라고 한다. N개의 수 중 좋은 수가 총 몇 개인지 출력하시오.

입력
1 번째 줄에 수의 개수 N(1 <= N <= 2,000), 2번째 줄에 N개의 수의 값(Ai)이 주어진다(|Ai|<=1,000,000,000,Ai는 정수)

출력
좋은 수의 개수를 출력한다.

예제 입력 1

10 //수의 개수
1 2 3 4 5 6 7 8 9 10

예제 출력 1

1단계. 문제 분석하기

: N의 개수가 2,000개지만 -> 하나의 결과를 위한 시간 복잡도가 N^2보다 작아야 한다.

-> 최소의 시간 복잡도 O(nlogn)

->예외처리 : 정렬된 데이터에서 자기 자신은 제외해야 한다. -> 두 수의 합으로 표현되어야 하기 때문에

2단계. 손으로 풀어보기

수를 입력받아 배열에 저장 후 정렬
투 포인터를 배열의 양쪽 끝에 위치시키고, 포인터를 이동시키면서 탐색을 수행
# 투 포인터 이동 원칙
arr[i] + arr[j] > K : j--;
arr[i] + arr[j] < K : i++;
arr[i] + arr[j] ==K : i++; j--; count++;
포인터의 이동을 배열의 모든 수에 반복 [K가 N이 될 때까지]

3단계. 슈도코드 작성하기

N（배열의 데이터 개수）A[N]
배열 선언 for（N만큼 반복하기）
{
     A 배열에 데이터 저장하기
}
A 배열 정렬하기

for（N만큼 반복하기）
{
    변수 초기화하기（찾고자 하는 값 k, 포인터 i, 포인터 j）
    while（丄 < j）
    {
    if（A[i] + A[j] = 찾고자 하는 값）
        두 포인터 i, j가 k가 아닐 때 결팟값에 반영 및 while 문 종료하기
        두 포인터 i, j가 k가 맞을 때 포인터 변경 및 계속 수행하기
    else if（k M） 포인터 i 증가
    else 포인터 j 증가
	}
}
좋은 수의 개수 출력하기

package datastructure.ch03;

import java.util.Arrays;
import java.util.Scanner;

public class ds_q08 {
	public int solution(int[] arr) {
		int answer = 0;
		Arrays.sort(arr);
		
		for (int i = 0; i < arr.length; i++) {
			int p1 = 0;
			int p2 = arr.length - 1;
			
			while (p1 < p2) {
				int sum = arr[p1] + arr[p2];

				if (sum == arr[i]) {
					if (i != p1 && i != p2) {
						answer++;
						break;
					} 
					
					//같은 경우를 제외하므로, 증감 조건 분리해야한다.
					else if (p1 == i) {
						p1++;
					} else if (p2 == i) {
						p2--;
					}
				} else if (sum > arr[i]) {
					p2--;
				} else {
					p1++;
				}
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		ds_q08 T = new ds_q08();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();
		System.out.println(T.solution(arr));
	}

}

728x90

저작자표시 비영리

'Java > Java 알고리즘' 카테고리의 다른 글

[알고리즘] 3-1. 조합 : dim[i][j] = dim[i-1][j] + dim[i-1][j-1] (0)	2022.06.30
[알고리즘] 2-4. 슬라이딩 윈도우 # [+deque 데크 자료구조] (0)	2022.06.30
[알고리즘] 2-2. 구간 합 [경우의 수 구하기 (순열과 조합 이용)] (0)	2022.06.30
[알고리즘] 2-1. 배열과 리스트 (0)	2022.06.28
[알고리즘] 2. 자료구조 (0)	2022.06.28

Just do it, and then some

[알고리즘] 02-3. 투 포인터

'Java > Java 알고리즘' 카테고리의 다른 글

티스토리툴바

[알고리즘] 02-3. 투 포인터

'Java > Java 알고리즘' 카테고리의 다른 글

'Java/Java 알고리즘' Related Articles

티스토리툴바