[1940번] 주몽

✅ 투포인터

원칙은 아래와 같다.

조건) 각 값이 사용된 후 재사용이 없을 때 사용하면 좋고, 각 값을 정렬한 후에 사용하자. 

정렬 알고리즘은 O(nlogn) 만에 돌아가므로 15,000을 요구하는 이 문제에서는 충분히 사용할 만 하다.

- arr [startIndex] + arr [endIndex] < sum 

startIndex를 증가시킨다.
    
- arr [startIndex] + arr [endIndex] > sum 

endIndex를 감소시킨다.

- arr [startIndex] + arr [endIndex] == sum 

count 증가시킨다.
endIndex를 감소시킨다.
startIndex를 증가시킨다.

✅ 코드

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

public class extension {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int needNum = sc.nextInt();
		int[] uniqueNum = new int[num];

		for (int i = 0; i < num; i++) {
			uniqueNum[i] = sc.nextInt();

		}

		Arrays.sort(uniqueNum);

		int startIndex = 0, endIndex = num - 1, count = 0;

		for (int i = 0; i < uniqueNum.length; i++) {
			while (startIndex < endIndex) {
				int sum = uniqueNum[startIndex] + uniqueNum[endIndex];
				if (sum > needNum) {
					endIndex--;
				} else if (sum < needNum) {
					startIndex++;
				} else {
					count++;
					endIndex--;
					startIndex++;
				}
			}
		}

		System.out.println(count);


	}
}

👾 주의

투 포인터가 서로를 지나면 이전의 값을 한 번 더 셈 해주는 것이 되므로 시작 인덱스가 항상 끝 인덱스보다 작아야 하는 것 에 유의하자