백준 1253번(좋다)[JAVA]

풀이

투 포인터 개념을 활용해야 하는 문제이다. 투 포인터의 개념은 배열을 탐색할 때 인덱스 포인터를 두개를 사용해서 배열을 탐색하는 개념이다.

근데 이 문제에서는 포인터가 3개..라고 볼 수도 있을 것 같다.

탐색 방법

1. 입력 받은 배열을 오름차순으로 정렬하여, 두개의 포인터 이동의 기준을 잡는다. 정렬하는 이유는, 찾고자 하는 값보다 두개의 포인터가 가리키는 원소의 합이 클 경우, 오른쪽에 있는 포인터(end포인터)를 왼쪽으로 옮기면서 원소의 합을 줄일 수 있고, 반대로 두개의 포인터가 가리키는 원소의 합이 찾고자하는 값보다 작을 경우, 왼쪽에 있는 포인터(start포인터)를 오른쪽으로 옮기면서 원소의 합을 키워가면서 원하는 값을 명확한 기준으로 찾을 수 있기 때문이다.
2. 그 후 찾고자 하는 값을 입력받은 배열에서 하나씩 꺼낸다.
3. 찾고자 하는 값(find)를 두개의 포인터가 가리키는 원소들의 합과 비교한다.
   • 두 포인터가 가리키는 원소들의 합이 찾고자 하는 값(find)과 같을 경우 : 두 포인터가 가리키는 곳 중 하나라도 찾고자 하는 값(find)의 인덱스와 같으면, 자기 자신을 합에 포함하는 것이기 때문에, 두 포인터 모두 자기 자신을 가리키지 않도록 조건문을 하나 더 걸어서 결과값을 도출한다.

     예제 입력에는 나와있지 않아서, 이 경우를 생각해내는 데에 너무 힘이 들었다…

     ex) 0 0 1 6 7 8의 배열이 있으면 6을 찾는 데에 자기 자신 6이 들어갈 수 있다. 이 경우를 제외해야 한다. 이 예시에서는 end포인트가 6을 가리키고 있기 때문에, end를 감소시키면서 탐색한다.
     ex) 0 0 0 0 1 2의 배열이 있으면, 3번째 0을 찾는 데에 start포인터가 3번째를 가리키고, end포인터가 4번째를 가리키고 있을 수 있다. 이런 경우 start포인터가 자기 자신을 가리키고 있으므로 start포인터를 증가 시킨다.

   • 두 포인터가 가리키는 원소들의 합이 찾고자 하는 값(find)보다 작을 경우 : 왼쪽 포인터(start)를 증가시켜서 다음 탐색 때 두 포인터 원소의 합이 find에 가까워지게 한다.
   • 두 포인터가 가리키는 원소들의 합이 찾고자 하는 값(find)보다 클 경우 : 오른쪽 포인터(end)를 감소시켜서 다음 탐색 때 두 포인터 원소의 합이 find에 가까워지게 한다.

소스 코드

import java.util.*;

public class 좋다 {
	public static void main(String[] arg) throws Exception{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		int cnt = 0;
		
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr);
		
		for (int i = 0; i < n; i++) {
			int find = arr[i];
			int start = 0;
			int end = n-1;
			
			while (start < end) {
				if (arr[start] + arr[end] == find) {
					if (start != i && end != i) {
						cnt++;
						break;
					}
					else if (end == i) {
						end--;
					}
					else {
						start++;
					}
				}
				else if (arr[start] + arr[end] < find) {
					start++;
				}
				else if (arr[start] + arr[end] > find) {
					end--;
				}
			}
		}
		System.out.println(cnt);
	}
}

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