백준 1940번(주몽)[JAVA]

풀이

투 포인터 개념을 도입해 사용하는 문제이다. 투 포인터 개념은 배열을 탐색할 때 인덱스 포인터를 두개를 사용하여 탐색하는 개념이다. 이 문제의 경우, n의 최대가 15,000이므로 정렬을 사용해서 투 포인터 개념을 사용하고자 한다. 입력받은 배열을 정렬한 후, 한 포인터는 배열의 첫번째(start), 다른 한 포인터는 배열의 마지막 원소(end)를 가리키면서 배열을 탐색한다.
투 포인터의 탐색 방법

1. 두 포인터가 가리키는 원소 값이 m과 같을 경우 : 결과값인 cnt를 증가시킨다. 이미 두 포인터의 원소의 합이 m이므로, start와 end를 모두 움직여서 다른 값을 도출해야한다. 이 중 하나의 포인터만 움직여도 상관 없지만, 하나만 움직이면 의미없는 비교가 되므로 비교 연산이 추가된다.
2. 두 포인터가 가리키는 원소 값이 m보다 작을 경우 : start를 증가시킨다.(정렬된 배열이므로, start를 증가시켜서 arr[start]+arr[end]의 값을 키우면서 m에 다가간다)
3. 두 포인터가 가리키는 원소 값이 m보다 클 경우 : end를 감소시킨다.(정렬된 배열이므로, 이 경우에는 end를 감소 시켜서 arr[start] + arr[end]의 값을 줄이면서 m에 다가간다)

소스 코드

import java.util.*;

public class 주몽 {
	public static void main(String[] arg) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] arr = new int[n];
		int start = 0;
		int end = n-1;
		int cnt = 0;

		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr);
		//1 2 3 4 5 7
		while (start != end) {
			if (arr[start] + arr[end] == m) {
				cnt++;
				start++;
                end--;
			}
			else if (arr[start] + arr[end] < m) {
				start++;
			}
			else if (arr[start] + arr[end] > m) {
				end--;
			}
		}
		System.out.println(cnt);
	}
}

태클 감사합니다.
조언 환영입니다.