문제 링크 : https://www.acmicpc.net/problem/2470
코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!
문제 정의
- 개의 용액 존재
- 두 용액을 혼합했을 때 값이 가장 0에 가까운 값을 출력
각 용액이 다음과 같은 값을 가질 때는
-1이 가장 0에 근접한 수가 됩니다.
접근 방법
가장 먼저 봐야할 것은 의 범위입니다.
1억 번의 연산이 1초라고 생각했을 때
이 10만인 경우 의 풀이법은 TLE가 발생합니다.
따라서 최대 의 시간 복잡도를 가지는 알고리즘을 사용할 수 있습니다.
알고리즘 선택
저는 두 가지 방법을 떠올렸습니다.
- 이분 탐색
- 투 포인터
이분 탐색
- 용액을 정렬 후
- 하나의 용액을 선택하고 다른 하나의 용액을 이분 탐색으로 찾는 방법
- 정렬 후 탐색 로직
투 포인터
- 용액을 정렬한 후
- 투 포인터로 0에 가까운 값들을 찾아나가는 방법
- 정렬 후 탐색 로직
저는 구현이 비교적 간단하면서도
시간 복잡도가 낮은 투 포인터 방식을 사용했습니다.
투 포인터란?
접근 방법
초기화
- Solutions 배열: 용액의 특성값을 담는 배열
- answer 배열: 현재 탐색까지의 두 용액의 혼합값이 가장 0에 가까운 두 용액
- min: 현재 탐색까지의 두 용액의 0에 가장 가까운 혼합값
// 용액을 정렬
Arrays.sort(solutions);
// 투 포인터 시작, 종료 인덱스 선언
int start = 0;
int end = N-1;투 포인터 로직을 수행하기 이전에 다음을 수행합니다.
- 용액 배열 정렬
- 시작, 종료 인덱스 초기화
핵심 로직
// 투 포인터 로직
// start 가 end 보다 크거나 같을 때 종료
while (start < end) {
// 두 용액이 혼합됐을 때의 특성값, 그리고 특성값에 대한 절댓값
long two_solutions = solutions[start] + solutions[end];
long solutions_abs = Math.abs(two_solutions);
// 0인 경우 정답을 변경하고 종료
if (two_solutions == 0) {
answer[0] = solutions[start];
answer[1] = solutions[end];
break;
}
else {
// 최솟값 갱신 (0에 더 가까운 값을 찾은 경우)
if(solutions_abs < min) {
min = solutions_abs;
answer[0] = solutions[start];
answer[1] = solutions[end];
}
// two_solution 이 양수인지 음수인지 여부에 따라 시작, 종료 인덱스 증감
// 음수일 경우 => 값이 더 커져야 하므로 start 증가
// 양수일 경우 => 값이 작아져야 하므로 end 감소
if (two_solutions < 0) start++;
else end--;
}
}
two_solutions: 두 용액이 혼합됐을 때의 특성값solutions_abs: 두 용액이 0에 얼마나 가까운지 확인하기 위한 절댓값
이 문제에서 로직은 두 가지로 나뉩니다.
- 두 용액의 합성값이 0인 경우
- 두 용액의 합성값이 0이 아닌 경우
1. 두 용액의 합성값이 0인 경우
0인 경우는
즉시 용액을 정답배열에 넣고 종료합니다.
2. 두 용액의 합성값이 0이 아닌 경우
0이 아닌 경우
최솟값인지 아닌지에 따라 조건이 바뀝니다.
최솟값인 경우: 최솟값 갱신을 수행합니다. (min, answer 갱신)
최솟값이 아닌 경우: 합성값이 0보다 크면 end 감소, 작으면 start 증가
예시
아래와 같은 입력이 주어진다고 가정하겠습니다.
입력
5
-2 4 -99 -1 981. 초기화
투 포인터 로직을 수행하기 전 초기화를 합니다.
- 용액 배열 정렬
min초기화answer초기화startend초기화
2. 투 포인터 수행
이제 투 포인터를 수행해보겠습니다.
처음은 start end 인덱스에 존재하는 두 용액 값을 합하면 -1
최솟값은 절댓값인 1이 됩니다.
합성값이 0이 아니고 음수이기 때문에
0에 가까운 수를 찾으려면 용액값이 더 커야하므로
start 인덱스를 증가시킵니다.
다음 두 용액의 비교입니다.
0이 아니면서 최솟값보다 큰 수인 97이 나왔기 때문에
정답 갱신은 없고
두 합성값이 양수이므로
0에 가까운 수를 찾으려면 이전보다 더 낮은 용액을 선택해야하므로
end를 감소시킵니다.
다음 두 용액을 비교해보면
0이 아니면서 최솟값보다 큰 수인 2가 나왔기 때문에
정답 갱신은 없고
두 합성값이 양수이므로
0에 가까운 수를 찾으려면 이전보다 더 낮은 용액을 선택해야하므로
end를 감소시킵니다.
다음 두 용액을 비교해보면
0이 아니면서 최솟값보다 큰 수인 2가 나왔기 때문에
정답 갱신은 없고
두 합성값이 음수이므로
0에 가까운 수를 찾으려면 이전보다 더 높은 용액을 선택해야하므로
start를 증가시킵니다.
start와 end가 가리키는게
두 용액이 아닌 같은 용액을 가리키므로
더 이상 비교할 수 없습니다.
지금까지 비교한 용액들 중 가장 0에 가까운 수 였던
-99와 98을 정답으로 출력합니다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 변수 선언
int N = Integer.parseInt(br.readLine());
long[] solutions = new long[N];
long[] answer = new long[2];
long min = Long.MAX_VALUE;
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
solutions[i] = Integer.parseInt(st.nextToken());
}
// 용액을 정렬
Arrays.sort(solutions);
// 투 포인터 시작, 종료 인덱스 선언
int start = 0;
int end = N-1;
// 투 포인터 로직
// start 가 end 보다 크거나 같을 때 종료
while (start < end) {
// 두 용액이 혼합됐을 때의 특성값, 그리고 특성값에 대한 절댓값
long two_solutions = solutions[start] + solutions[end];
long solutions_abs = Math.abs(two_solutions);
// 0인 경우 정답을 변경하고 제거
if (two_solutions == 0) {
answer[0] = solutions[start];
answer[1] = solutions[end];
break;
}
else {
// 최솟값 갱신
if(solutions_abs < min) {
min = solutions_abs;
answer[0] = solutions[start];
answer[1] = solutions[end];
}
// two_solution 이 양수인지 음수인지 여부에 따라 시작, 종료 인덱스 증감
// 음수일 경우 => 값이 더 커져야 하므로 start 증가
// 양수일 경우 => 값이 작아져야 하므로 end 감소
if (two_solutions < 0) start++;
else end--;
}
}
System.out.println(answer[0] + " " + answer[1]);
}
}