문제: https://www.acmicpc.net/problem/2467
2467번: 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -
www.acmicpc.net
투 포인터에 대해서 공부한다고 했을 때 알고리즘 단톡방에 계신 분께서 추천해주신 문제다.
필자는 이 문제로 두개의 포인터가 같은 방향으로 이동하는 것과 서로 다른 방향에서 진행되는 알고리즘의 차이를 알 수 있었다.
당연한 얘기지만 이 문제를 풀 때 정말 머리를 쥐어 싸맸던 것으로 기억한다.
이제 따끈따끈하게 실버가 된 뉴비에게 골드 문제는 아직까지도 많이 어려웠다.
하지만 나도 할 수 있었던 만큼 다른 분들도 투 포인터 알고리즘을 알고만 있다면 할 수 있을 것이라고 생각한다.
지금부터 문제 분석부터 차근차근 넘어가보자.
일단 문제에서 요구하는 것 자체는 그리 어렵지 않다.
두 용액의 합이 최대한 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);
}
}'☕JAVA > 👩💻BOJ(백준)' 카테고리의 다른 글
| [투 포인터, JAVA] 백준 - 1940 (2) | 2022.09.20 |
|---|---|
| [투 포인터, JAVA] 백준 - 2018 (0) | 2022.09.19 |
| [구간합, JAVA] 백준 - 10986 (0) | 2022.08.20 |
| [구간합, JAVA] 백준 - 11660 (0) | 2022.08.17 |
| [구간합, JAVA]백준 - 11659번 (0) | 2022.08.16 |
