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

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

1940번: 주몽

---

수 들의 합 5를 클리어하고 단톡방에 계신 분들이 추천해주시는 몇몇 문제들을 푼 다음 풀게 되었던 문제다.
이 문제를 계기로 나는 투 포인터가 같은 방향에서  시작하는 것과 서로 다른 방향에서 진행하는 것에 대한 의문점을 갖게 되었다.
그 해답을 찾기 위해 용액이라는 문제를 풀게 되었던 것이다. 용액이 어떤 문제인지 궁금한 분들은 용액 글씨를 클릭해,
문제 풀이를 보면 될 것 같다.

서론은 이쯤에서 그만두고 이제 본론으로 넘어가보자.
문제를 먼저 분석해보자면, 재료의 개수가 N이고 갑옷을 만드는데에 필요한 수 M인데,
N개의 재료번호의 합이 M이 되는 것이 총 몇 개인지 물어보는 문제다.
사실 투 포인터는 배열을 정렬하는 로직이 필요한 알고리즘이다.
왜냐하면 더해지는 값과 목표값의 차이에 따라서 두 개의 포인터를 움직여야 하기 때문이다.
따라서 정렬을 해준 다음에 투 포인터 알고리즘을 이용해서 풀면 된다.
투 포인터 알고리즘에 대해서 잘 모르시는 분들은 해당글의 "투 포인터" 글씨를 클릭해주면 자세한 설명을 읽을 수 있을 것이다.

문제 풀이도 끝났으니, 이제 코드를 봐보자.

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

public class BOJ_1940_4 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 1940
		
        //숫자를 빨리 입력받기 위해서 BufferedReader 클래스 객체 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        //BufferedReader 클래스는 한 줄씩 입력을 받고,
        //한줄에 하나의 숫자만 입력을 받는다면 StringTokenizer로 숫자들을 파싱할 이유가 없음.
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
        
        //재료의 번호들을 저장할 배열 선언
		int[] nums = new int[N];
		
        //한 줄에 여러 숫자들을 입력받으므로 StringTokenizer 클래스 객체 선언
		StringTokenizer st = new StringTokenizer(br.readLine());
        
        //입력받은 여러개의 숫자들을 각각 배열의 매 칸마다 저장함
		for(int i=0; i<N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
        //오름차순으로 정렬해준다. 투포인터 알고리즘을 이용하기 위해서다.
		Arrays.sort(nums);
		
        //start는 투 포인터 시작 인덱스, end는 투 포인터 끝 인덱스,
        //answer는 nums[start] + nums[end]가 M이랑 같을 때를 카운트하는 변수다.
		int start = 0, end = N-1, answer = 0;
		
        //투 포인터 알고리즘
		while(start < end) {
        	//sum은 반복문이 돌 때마다 바뀌어야 하며,
            //sum에 대한 start와 end에 대한 연산을 줄이기 위해
            //sum을 반복문 안에다 선언하면서 초기화를 해준다.
			int sum = nums[start] + nums[end];
			
            //sum이랑 M이 같다면 +1해주고 start를 증가시켜서
            //다음 경우의 수로 넘어간다.
            		if(sum == M) {
				++answer;
				++start;
			} else if(sum < M) {
            	//sum보다 M이 크다면 이는 sum의 값을 늘려줘야 하므로,
                //start를 늘려준다.
				++start;
			} else {
            	//else라면 sum > M 경우만 남는데,
                //이는 sum의 값을 줄여줘야 하므로, end를 줄여준다.
				--end;
			}
		}
		
        //그렇게 반복문이 종료되면 answer를 출력해준다.
		System.out.println(answer);
	}

}