◎ 문제풀이
차례로 각 지점이 원으로 연결되어 있을 때, 두 지점 사이의 거리의 최댓값을 구하는 문제이다. 지점의 개수가 최대 5만개이니 두 지점의 모든 경우를 완전탐색하면 시간초과가 난다.
그러니 Two Pointer 알고리즘을 사용해보자.
Two Pointer 알고리즘은 두 지점의 경우 중에 비교할 가치가 있는 경우만 가지치기하여 탐색하는 알고리즘이다.
PointerA와 PointerB 사이의 거리는 두 가지가 있다.
PointerA지점의 오른쪽 경로 거리 = 1
PointerA지점의 왼쪽 경로 거리 = 17
최솟값이 공식거리이므로 두 지점 사이의 거리는 1이다.
그럼 PointerB를 한칸 이동해보자.
PointerA지점의 오른쪽 경로 거리 = 1 + 5 = 6
PointerA지점의 왼쪽 경로 거리 = 17 - 5 = 12
두 지점 사이의 거리는 6이다.
PointerA지점의 오른쪽 경로 거리 = 6 + 7 = 13
PointerA지점의 왼쪽 경로 거리 = 12 - 7 = 5
오른쪽 경로가 왼쪽 경로보다 같거나 커지면 더이상의 탐색은 무의미하다.
탐색할수록 오른쪽 경로는 증가하고 왼쪽 경로는 감소한다. 그런데 두 지점의 공식거리는 최솟값이고 문제의 목적은 두 지점의 최대거리를 구하는 것이다. 왼쪽이 오른쪽보다 작아지면 PointerA를 고정하고 PointerB를 이동해봤자 계속 작아진 왼쪽 경로만 공식거리가 된다. 그러므로 최대값은 더이상 나오지 못한다.
그러므로 고정되어 있던 PointerA를 움직이고 PointerB는 고정한다. 그러면 왼쪽경로가 증가하고 오른쪽 경로가 줄어드니, 다시 두 지점사이의 비교가 유의미해진다. 이렇듯, 투포인터 알고리즘은 무의미한 비교를 가지치기 하므로써 탐색속도를 올릴 수 있다.
그럼 이제 PointerA를 움직이자.
PointerA지점의 오른쪽 경로 거리 = 13 - 1 = 12
PointerA지점의 왼쪽 경로 거리 = 5 + 1 = 6
오른쪽 경로가 더 크므로 오른쪽 경로를 고정하고 왼쪽 경로를 이동한다. 이런 원리로 투포인터 알고리즘을 사용하면 필요한 비교만 할 수 있게되어 탐색속도가 빨라진다.
◎ 코드
import java.util.Scanner;
import static java.lang.Math.*;
//BOJ2118 두 개의 탑
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] dist = new int[n];
int sum = 0;
int ans = 0;
for(int i=0;i<n;i++){
dist[i] = sc.nextInt();
sum += dist[i];
}
int pointerA = 0;
int pointerB = 1;
int right = dist[pointerA];
int left = sum - right;
// PointerA를 기준으로 탐색
while(pointerA < n){
ans = max(ans, min(right,left));
// 왼쪽 경로가 크면 PointerB를 이동
if( right < left ){
right += dist[pointerB];
left -= dist[pointerB];
pointerB++;
pointerB %= n;
}
// 오른쪽 경로가 크면 PointerA를 이동
else{
right -= dist[pointerA];
left += dist[pointerA];
pointerA++;
}
}
//결과 출력
System.out.println(ans);
}
}
'문제풀이 > TwoPointer' 카테고리의 다른 글
[PS] BOJ2230 수 고르기 ( TwoPointer ) with JAVA (0) | 2023.09.15 |
---|---|
[PS] BOJ2470 두 용액 ( Two Pointer ) with JAVA (0) | 2023.07.13 |