[알고리즘] 투 포인터(Two Pointer) - JAVA(자바)

투 포인터(Two Pointer)

• 배열 또는 리스트에서 두개의 포인터의 위치를 기록해가면서 원하는 결과를 찾아내는 알고리즘 (2가지 방법존재)  
  • 시작할 때, 정렬된 배열에서 처음 인덱스와 마지막인덱스를 두 개의 포인터가 가리키는 경우
  • 시작할 때, 처음 인덱스를 두 개의 포인터가 모두 가리키는 경우
• 시간복잡도는 O(n)이다. (부분 배열을 이용해 탐색하기 때문에 O(n))
  • 보통 선형 공간 탐색시 시간복잡도가 O(n²)이상이 되는 부분을 O(n)으로 줄이기 위해 사용된다.
  • 이를 저격하는 문제는 투 포인터를 사용하지 않으면 시간초과가 발생한다.

 

 

두 포인터를 사용한 풀이에 대한 자세한 설명은 아래 글에 작성해두었다.

 

N이 되는 연속된 자연수의 합 - 처음 인덱스를 두 개의 포인터가 모두 가리키는 경우

https://chobo24.tistory.com/entry/%EB%B0%B1%EC%A4%80-2018%EB%B2%88-%EC%88%98%EB%93%A4%EC%9D%98-%ED%95%A9-5-JAVA%EC%9E%90%EB%B0%94

[백준] 2018번 수들의 합 5 - JAVA(자바)

[작성한 코드]

import java.io.*;

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int count=1; //가짓수 1개는 자기자신을 의미
		
		//투포인터 풀이
		int start = 0; //시작 포인터
		int end = 0; //종료 포인터
		int sum=0;
		
		while(end<N) {
			//sum이 더 크다면 시작포인터 증가
			if(sum>N) {
				//합의 시작 부분이 바뀌었기 때문에 원래 시작한 수는 빼줌
				sum-=start;
				start++;
			}
			//sum이 작다면 종료포인터 증가
			else if(sum<N){
				end++;
				//연속된 합의 마지막 수 새로 더함
				sum+=end;
			}
			else { //sum==N이라면
				count++;
				end++;
				sum+=end;
			}
		}
		System.out.println(count);
	}
}

 

 

 

 

두 개의 수가 M이 되는 경우 - 정렬된 배열에서 처음 인덱스와 마지막인덱스를 두 개의 포인터가 가리키는 경우

https://chobo24.tistory.com/entry/%EB%B0%B1%EC%A4%80-1940%EB%B2%88-%EC%A3%BC%EB%AA%BD-JAVA%EC%9E%90%EB%B0%94

[백준] 1940번 주몽 - JAVA(자바)

[작성한 코드]

import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[N];
		//재료들 고유 번호 저장
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		int start = 0; //시작포인터 - 작은 값 인덱스
		int end = N-1; //종료포인터 - 큰 값 인덱스
		int count = 0;
		
		while(start<end) { //양쪽 포인터가 좁혀지다가 같아지기전까지 반복
			int sum = arr[start]+arr[end];
			if(sum>M) { //sum이 크다면 종료포인터를 왼쪽으로 이동
				end--;
			}
			else if(sum<M) { //sum이 작다면 시작포인터를 오른쪽으로 이동
				start++;
			}
			else { //sum==M이면 count증가 시작포인터와 종료포인터 모두 이동
				count++;
				end--;
				start++;
			}
		}
		
		System.out.println(count);
	}
}

 

 

 

 

다른 두 수의 합으로 표현되는 수 찾기 - 정렬된 배열에서 처음 인덱스와 마지막인덱스를 두 개의 포인터가 가리키는 경우

https://chobo24.tistory.com/entry/%EB%B0%B1%EC%A4%80-1253%EB%B2%88-%EC%A2%8B%EB%8B%A4-JAVA%EC%9E%90%EB%B0%94

[백준] 1253번 좋다 - JAVA(자바)

[작성한 코드]

import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		long[] arr = new long[N];
		int count = 0; //좋다에 해당하는 수 개수
		StringTokenizer st = new StringTokenizer(br.readLine());
		//N개의 수 입력받아 저장
		for(int i=0; i<N; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		
		//투 포인터 사용을 위해 오름차순 정렬
		Arrays.sort(arr);
		for(int i=0; i<N; i++) {
			int left = 0; //왼쪽포인터 - 작은 값 인덱스
			int right = N-1; //오른쪽포인터 - 큰 값 인덱스
			
			while(left<right) { //양쪽 포인터가 좁혀지다가 같아지기전까지 반복
				long num = arr[left]+arr[right];
				
				
				//num이 크다면 right포인터를 왼쪽으로 이동
				if(num>arr[i]) right--;
				
				//num이 작다면 left포인터 오른쪽으로 이동
				else if(num<arr[i]) left++;

				else { //num==arr[i]이면
					if(left==i) left++; // left와 같다면 오른쪽으로 이동
					else if(right==i) right--; //right과 같다면 왼쪽으로 이동 
					
					//자기자신을 제외하고 다른 두수의 합일 때, 좋다(GOOD)인 수로 판정 - 반복문 종료
					else{
						count++;
						break;
					}
				}
				
			}
		}
		
		System.out.println(count);
	}
}