[Java] 자바에서 투 포인터 알고리즘 구현하기

2023-02-16

---

사진: Unsplash 의 Anita Austvika

---

1. 문제설명

 

일반적으로 투 포인터 알고리즘은 1차원 수열에서 목표값을 찾을 때 사용한다. 대표적인 예로 구현을 해보자. 아래의 백준문제를 참고해서 구현했다.

 

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

---

구현은 아래와 같이 구현했다. 매 분기마다 총합을 비교하며 총합이 타깃보다 클 경우 현재 시작포인터의 배열값을 차감하고 시작포인터를 증가시키고 총합이 타깃보다 작거나 같을 경우 마지막포인터 배열값을 더하고, 마지막 포인터를 하나 더해준다.

 

	@Test
	public void Test(){
		int [] arr = {3,2,1,4,1,2,5,6}; //수열
		int target =5; //찾고자 하는 값
		int start = 0; //시작 포인터
		int end = 0; // 끝나는 포인터
		int sum = 0; // 합
		int count = 0; // 몇개나 되는지
		while (start < arr.length) {//시작포인터가 전체 수열보다 작을동안
			if (sum > target || end == arr.length) {// 총합이 목표값보다 크거나 마지막포인터가 전체길이에 도달시
				sum -= arr[start++];//총합에 시작포인터가위치한 값 빼고 시작포인터 더하기
			} else { //총합이 목표값보다 작거나 같을경우
				sum += arr[end++];//총합에 마지막포인터값 도하고 마지막포인터하나 더하기
			}
			if (sum == target) //총합이 목표값에 도달했을경우
				count++;
		}
		System.out.println(count);
	}

---

메인 이미지 출처 : 사진: Unsplash의Anita Austvika