Life Study

문제: https://www.acmicpc.net/problem/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);
	}
}

문제: https://www.acmicpc.net/problem/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);
	}

}

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

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

문제를 보면 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);
	}
}

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

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

투 포인터에 대해서 공부한다고 했을 때 알고리즘 단톡방에 계신 분께서 추천해주신 문제다.
필자는 이 문제로 두개의 포인터가 같은 방향으로 이동하는 것과 서로 다른 방향에서 진행되는 알고리즘의 차이를 알 수 있었다.
당연한 얘기지만 이 문제를 풀 때 정말 머리를 쥐어 싸맸던 것으로 기억한다.
이제 따끈따끈하게 실버가 된 뉴비에게 골드 문제는 아직까지도 많이 어려웠다.
하지만 나도 할 수 있었던 만큼 다른 분들도 투 포인터 알고리즘을 알고만 있다면 할 수 있을 것이라고 생각한다.
지금부터 문제 분석부터 차근차근 넘어가보자.

일단 문제에서 요구하는 것 자체는 그리 어렵지 않다.
두 용액의 합이 최대한 0과 가까우면 되는 문제이다. 출력은 그 두 용액을 출력하면 된다.
하지만 여기서 문제점이 생긴다. 더해서 0과 가장 가까운 값을 찾으려면 어떻게 해야 하지?
즉, 우린 여기서 투 포인터 + 근사값 알고리즘 이렇게 같이 알아야 이 문제를 풀 수 있다.
물론 이분탐색으로도 풀 수 있지만, 일단 이 글에선 투 포인터로 주제를 잡고 풀겠다.

0과 근사한 값을 구하려면 어떻게 해야 할까?
일단 0에서 얼마나 떨어져있는지를 체크하고, 이 값과 비교할 이전의 최소 거리값이 있어야 할 것이다.
그러기 위해선 우린 절대값을 사용해야 한다. 왜냐하면 절대값 자체가 수직선의 거리를 뜻하기 때문이다.
그리고 더해서 나온 최소값이 이전의 최소 거리값보다 작다면 최소값을 바꿔주고 더해지는 값들을 답으로 지정하면 된다.
그리고 우린 그 더해지는 값들을 투 포인터로 찾으면 된다. 말로 하면 어렵지만, 그림으로 보면 쉬울 것이다.

정리하자면
① 서로 더해지는 숫자들은 투 포인터 알고리즘을 이용해서 바꿔준다. (0을 기준으로)
② 더한 값이 0이랑 가까운지 체크하는건 근사값 알고리즘을 사용한다.

그럼 이제 코드를 살펴보자.

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

public class BOJ_2467_4 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 2467
		
        //입력을 빨리 받기 위한 BufferedReader 클래스와 숫자들을 파싱할 STringTokenizer 클래스 객체
		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]; //용액 개수만큼의 배열 선언
		
        //st 변수 초기화. BufferedReader 클래스는 한 줄씩만 읽어오기 때문에,
        //입력받는 줄이 달라진다면 st를 초기화해줘야 한다.
		st = new StringTokenizer(br.readLine());
        
        //용액의 숫자들을 입력받는 반복문
		for(int i=0; i<N; i++) { 
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
        //start는 배열의 시작 인덱스, end는 배열의 끝 인덱스,
        //asnwer1, answer2는 0과 더해서 0과 가장 가까운 2개의 용액 값을 저장할 변수들이다.
        //min은 이전 최소값이다. 하지만 지금은 비교 대상이 없기 때문에(아직 반복문에 들어가지 않음) 
        //Long의 최대값으로 저장해놓은 상태다.
		int start = 0, end = N-1, answer1 = 0, answer2 = 0;
		long min = Long.MAX_VALUE;
		
        //투 포인터 알고리즘 + 근사값 알고리즘
		while(start < end) {
        	//더한 값은 반복이 돌 때마다 변해야 하므로 반복문 안에서 선언하고 값을 더해준다.
            //abs는 더한 값의 절대값이다.
            //따로 저장하는 이유는 sum 값의 범위에 따라서 
            //start를 증가 시키거나 end를 감소시켜야 하기 때문이다.
			long sum = nums[start] + nums[end];
			long abs = Math.abs(sum);
			
            //만약에 이전 합이 현재 더한 것보다 크다면 - 새로운 최소값 탄생
            //min의 값을 바꿔주고 answer1, 2에다가 현재 용액의 값들을 저장해준다.
            //저장해주고 만약 sum이 0이라면 이미 0과 가장 가까운 용액의 값을 찾은 것이므로
            //반복문을 종료시켜준다.
			if(abs < min) {
				min = abs;
				answer1 = nums[start];
				answer2 = nums[end];
				
				if(sum == 0) {
					break;
				}
			}
			
            //만약에 sum이 0보다 작다면 - 0과 가장 가까운 값이 되어야 하므로
            //0보다 작은 값이 나온다면 start 인덱스를 증가시켜주고,
            //반대의 경우엔 end를 줄여준다.
			if(sum < 0) {
				++start;
			} else {
				--end;
			}
		}
		
        //반복문이 종료된다면 두 용액들을 출력해준다.
		System.out.println(answer1+" "+answer2);
	}
}

지금 3~4일째 투포인터 알고리즘에 대해 열심히 삽질중이다.
사실 약속도 이리저리 생기고 공부도 같이 하느라 정신이 좀 많이 없었긴 했다.
알고리즘 단톡방에서 조언을 들었다. 슬라이딩 윈도우 알고리즘이랑 투 포인터 알고리즘이랑 같은건데,
다른 점이라곤 그 투포인터 사이의 간격을 유지하면서 탐색하느냐 간격을 유지하지 않고 자유롭게 탐색하느냐의
차이라는 조언이었다. 그리고.. 슬라이딩 윈도우는 카카오 같은 대기업이 아니라면 잘 나오지 않는 유형이라는 조언도 함께 들었다. 하지만 투포인터와 연결되어있다면 결국 투포인터의 개념을 마스터한다면 슬라이딩 윈도우의 개념도 같이 마스터하는 것이 되는 것이기 때문에 잘 안나와도 딱히 상관없을 것 같긴 하다.

아마 그래서 투포인터를 어느정도 풀 수 있게 된다면 슬라이딩 윈도우도 함께 삽질하고,
블로그에 연결해서 글을 쓸 것 같다.

(죽여줘....)