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

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

2018번: 수들의 합 5

---

책에서 투 포인터에 들어갈 때 가장 처음으로 나오는 문제다.
문제는.. 알고리즘이 매우 간단하다며 바로 실전 문제를 풀어보자는 말과 함께 등장하는 문제라는 것이다.
당황스럽지만 우리는 풀어야 한다.

문제를 보면 15를 표현하는 방법은 여러개가 있다고 한다. 7+8, 4+5+6, 1+2+3+4+5.
이 방법들이 총 몇 개인지 출력하면 되는 간단한 문제이다.
문제로는 간단하지만 막상 짜려고 하면 잘 모르겠는게 사실이니, 자세한 투 포인터의 개념은 "투 포인터" 글씨를 눌러주길 바란다.
배경색으로 입혀져있는 투 포인터 글씨들은 모두 그와 해당하는 글의 링크로 되어 있으니 참고 바란다.

그럼 이제 문제를 풀기 위해 어떤 개념이 필요한지 알았으니, 어떤 방식으로 짜야 하는가를 알아보자.
이 문제는 같은 방향에서 진행하는 투 포인터 흐름으로 알고리즘을 짜는 것이 편하다.
왜냐하면, 예제를 기준으로 누적해서 더한 것이 15가 되는지 체크를 해줘야 하기 때문이다.

정리하자면
•순서대로 누적합을 해서 N을 찾는 것이기 때문에 진행방향이 같은 투 포인터 알고리즘으로 진행하는 것이 편하다.

나머지는 코드로 알아보자.
코드는 총 2개의 버전이 있다.
첫번째 버전은 배열을 쓰지 않은 풀이이고, 두번째 버전은 배열을 사용한 풀이이다.

import java.io.*;

public class BOJ_2018_5 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 2018
		
        //입력을 빨리 받기 위해서 BufferedReader 클래스 객체를 선언해준다.
        //여러 숫자들을 한 줄에 여러개를 받으면 숫자들을 파싱할 필요가 있지만,
        //이번엔 입력을 한 줄에 한번만 받기 때문에 StringTokenizer 클래스 객체는 선언하지 않는다.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        //한 줄에 숫자 하나를 입력받은 것을 int형으로 형변환시켜주고 N에 저장한다.
		int N = Integer.parseInt(br.readLine());
		
        //start는 시작 숫자, end는 끝 숫자, sum은 start와 end를 더한 값, 
        //answer는 더해서 N이 되는 개수에 대한 변수다.
		int start = 1, end = 1, sum = 1, answer = 1;
		
        //투 포인터 알고리즘
        //start < N을 조건으로 달은 이유는 while문은 반복문 내용이 진행되다가 조건에 어긋나면
        //바로 반복문이 종료되는 것이 아니기 때문에 start <= N 조건으로 하지 않았다.
		while(start < N) {
        	//start 숫자와 end 숫자를 더한 값이 N과 같으면
            //answer를 늘려주고 start를 제거해준다.
            //왜냐하면 이미 현재 시작항을 포함한 end값까지 더한 경우를 answer에 추가했기 때문이다.
            //따라서 제거해준 다음, start를 하나 늘려서 다음 케이스를 찾는다.
			if(sum == N) {
				++answer;
				sum -= start;
				++start;
			} else if(sum < N) {
            	//sum이 N보다 작다면 sum을 늘려줘야 하므로 end를 늘려줘야 한다.
                //늘려준 다음, sum에 end를 더해준다.
				++end;
				sum += end;
			} else {
            	//그 밖의 케이스라면 sum > N인데, 이 경우에는 숫자를 줄여줘야 하기 때문에
                //start를 sum에서 제거해주고
                //start를 1씩 늘려준다.
				sum -= start;
				++start;
			}
		}
		
        //그렇게 구해진 답을 출력해준다.
		System.out.println(answer);
	}
}

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

public class BOJ_2018_3 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 2018번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int[] nums = new int[N+1];
		
        //배열 각 칸마다 숫자를 순서대로 저장해준다.
		for(int i=0; i<=N; i++) {
			nums[i] = i;
		}
		
        //sum이 nums[0]인 이유는 sum이 0이게 되면 배열의 첫 항이 
        //누적합에 들어가지 못하기 때문이다.
		int start = 0, end = 0;
		int sum = nums[0];
		int answer = 1;
		
        //투 포인터 알고리즘
		while(end <= N-1) {
			if(sum == N) {
				++answer;
				++end;
				sum += nums[end];
			} else if(sum < N) {
				++end;
				sum += nums[end];
			} else if(sum > N) {
				sum -= nums[start];
				++start;
			}
		}
		
		System.out.println(answer);
	}
}

이 때 두번째 코드보단 첫번째 코드가 메모리도 덜 잡아먹으며 속도도 좀 더 빠르기 때문에,
책에서는 첫번째 버전을 채택한게 아닐까 싶다.