[투 포인터, JAVA] 백준 - 1253

문제: https://www.acmicpc.net/problem/1253

1253번: 좋다

---

책에서 나오는 투 포인터 마지막 문제다. 책에서는 골드 3이라고 되어있는데, 현재는 골드 4로 내려갔다.
따끈따끈하게 실버로 올라온 뉴비에겐 솔직히 이 문제 너무 어려웠다.
책에 있는 풀이를 봐도 이해가 안됐다. 사실 한번 급하게 삽질을 끝낸 적은 있었는데,
다시 하려니까 같은 곳에서 해맨 것이다.

암튼 서론은 여기까지 하고 이제 본론으로 들어가자.
N을 입력받고 N개의 숫자들을 입력을 받고나서 이 숫자들끼리 서로 더해서 배열 안에 있는 요소가 되면
그게 문제에서 얘기하는 '좋은 수'인 것이다. 아 근데 자기 자신을 더해서 그 숫자가 나오는건 제외한다.
ex) 1+1 = 2, 2+2 = 4 ... 왜냐하면 문제에서 "수의 위치가 다르면 값이 같아도 다른 수이다."라고 했다.
이것을 대우로 뒤집어보면 "값이 달라도 같은수이면 수의 위치가 같다." 와 같은 문장이 된다.
결국 같은 수끼리는 더하면 안된다는 말이 문제에 내포되어있는 것이다.
다만 이건 필자같은 코린이들에게는 흐름이 좀 어려울 수 있으니, 그림으로 설명을 해보겠다.
N은 5이며 1 2 3 4 5 를 입력받았다고 가정하자.

알고리즘 흐름

그럼 이제 이 흐름들을 토대로 코드를 짜볼 시간이다.

import java.util.*;
import java.io.*;

public class BOJ_1253_4 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 1253
		
        //입력을 빨리 받기 위한 BufferedReader 클래스 객체 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        //한 줄에 하나만 입력 받는다면 StringTokenizer 클래스를 이용한
        //문자열 파싱이 필요가 없음.
        //nums라는 배열 선언 -> 숫자들을 저장할 배열
		int N = Integer.parseInt(br.readLine());
		int nums[] = new int[N];
		
        //한 줄에 여러개의 숫자들을 입력받아야 하기 때문에 파싱이 필요해짐.
        //StringTokenizer 클래스 객체 선언해줌.
        //for문을 이용해서 배열에 파싱한 숫자들을 하나씩 저장해준다.
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
        //배열의 내용물을 정렬해준다. 투 포인터 알고리즘을 사용해야 하기 때문이다.
        //answer는 '좋은 수'의 개수를 카운팅하기 위한 변수다.
		Arrays.sort(nums);
		int answer = 0;
		
        //서로 더해서 나와야 하는 값을 target 변수로 설정했음.
        //target에 배열의 각 요소 값들이 저장되어야 하므로 for문으로 
        //while(투 포인터 반복문)을 감싸준다.
		for(int i=0; i<N; i++) {
			int target = nums[i];
			int start = 0, end = N-1;
			
            //투 포인터 알고리즘
			while(start < end) {
            	//sum은 반복문 안에서 값이 계속 바뀌어야 함.
                //sum과 target의 값을 비교해야 하기 때문.
				int sum = nums[start] + nums[end];
				
                //sum이랑 target이 같을 경우엔 start와 end를 한번 더 체크해준다.
                //그래야 자기 자신과 더해서 좋은 수를 찾지 않을 수 있기 때문이다.
				if(sum == target) {
					if(start != i && end != i) {
						++answer;
						break;
					} else if(start == i) {
						++start;
					} else {
						--end;
					}
				} else if(sum < target) {
                	//sum값이 target보다 작다면 값을 늘려줘야 하므로,
                    //start를 늘려준다.
					++start;
				} else {
                	//else라면 sum > target 경우밖에 남지 않는데,
                    //이는 sum의 값을 줄여줘야 하므로 end를 줄여준다.
					--end;
				}
			}
		}
		
        //for문과 while문에서 나온 후 answer를 출력해준다.
		System.out.println(answer);
	}
}