백준 2118 두 개의 탑 (JAVA 자바 풀이)

백준 2118 두 개의 탑 (JAVA 자바 풀이)

 

---

문제

1번부터 N번까지의 지점이 있다. 각각의 지점들은 차례로, 그리고 원형으로 연결되어 있다. 이 지점들 중 두 곳에 두 개의 탑을 세우려고 하는데, 두 탑의 거리가 최대가 되도록 만들려고 한다.

 

지점들이 원형으로 연결되어 있기 때문에, 두 지점 사이에는 시계방향과 반시계방향의 두 경로가 존재한다. 두 지점 사이의 거리를 잴 때에는, 이러한 값들 중에서 더 작은 값을 거리로 한다.

 

연결되어 있는 두 지점 사이의 거리가 주어졌을 때, 두 탑의 거리의 최댓값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다.

출력

첫째 줄에 답을 출력한다.

 

 

---

 

 

💡 풀이 과정

 

문제의 요구사항을 먼저 이해해보자. 원형으로 배치된 지점들 중에 두 곳을 고르는 것이 첫 번째 액션이다. 단순히 생각해봤을 때 5개 중에서 2개를 고르는 케이스이기 때문에 5*4/2 = 10가지이다. 

 

즉 10가지 거리 중에 최대값을 고른다. 

 

1 2 3 4 5 케이스를 생각해보면 자리배치는 이렇게 될 것이다. 

 

_ 1 _ 2 _ 3 _ 4 _ 5 

 

이때 무조건 최대값이 아니라 정방향과 역방향 두가지 중 최소 값이 최대 값이 되어야 한다.

 

예제의 경우 2번 지점과 4번 지점을 골랐을 때 정방향에서 7, 역방향에서 8이 나오므로 최대값이 7이 되는데 이보다 큰 값이 없으므로 정답이 된다.

 

모든 케이스를 다 보는 경우라면 어떨까? 두 개의 반복문을 돌리면서 첫 번째 반복문은 i =0 일 때부터, 두 번째 반복문은 i +1 부터 탐색을 하는 것이다. 

 

다음과 같은 코드가 될 것이다. 

 

    for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int distanceClockwise = 0;
                int distanceCounterClockwise = 0;

                // 시계 방향 거리 계산
                for (int k = i; k != j; k = (k + 1) % N) {
                    distanceClockwise += distances[k];
                }

                // 반시계 방향 거리 계산
                distanceCounterClockwise = totalDistance - distanceClockwise;

                // 두 경로 중 더 작은 거리 선택
                int minDistance = Math.min(distanceClockwise, distanceCounterClockwise);

                // 최대 거리 갱신
                maxDistance = Math.max(maxDistance, minDistance);
            }
        }

 

지점 수 N개에 대해서, 시계 방향과 반 시계 방향의 거리를 비교하여 더 작은 값을 현재 최대 거리와 비교한다. 모든 지점 쌍에 대해 이 과정을 반복하여 최대 거리를 찾는다. 이때 시간 복잡도가 O(N^3)이므로 50,000개에 대해서 시간 초과를 받게 될 것이다. 

 

따라서 투포인터를 이용해서 풀이해보자.

 

먼저 환형 데이터의 경우 두 배로 늘려서 선형으로 작성하면 좀 더 편하게 계산할 수 있다. 

 

1 2 3 4 5 1 2 3 4 5 처럼 2배 인덱스에 대해 똑같은 값을 복사해준다. 

 

  int[] distances = new int[N * 2];
    
    int totalDistance = 0;
    for (int i = 0; i < N; i++) {
        distances[i] = parseInt(bufferedReader.readLine());
        distances[i + N] = distances[i]; // 원형 배열 생성
        totalDistance += distances[i];
    }

 

이렇게 배열을 두 배로 늘려서 작성하면 모듈러를 사용하지 않아도 되어 편리하자. 

 

이제 알고리즘 풀이에 필요한 아이디어를 생각해보자. 

 

각 지점에 대해 가장 먼지점이 나타나는 경우의 수는, 즉, 각 i에 대해서 j 중 최대 값이 된다고 할 때, 가장 먼 j는 절반의 거리를 경계로 가장 가까운 지점이 둘 중에 하나가 된다. 예를 들어서 문제의 예제의 경우 sum인 15 중 7.5 거리를 기준으로 나눴을 때 나뉘는 지점에서 정방향과 역방향 둘 중에 하나가 가장 멀다.

 

_ 1 _ 2 _ 3 _ 4 _ 5 

 

i가 0일 때를 생각해보면 j는 3 번이나 4번 자리여야 한다. 이때 min(6, 9) = 6, min(10, 5) = 5가 나온다. 

 

왜냐하면 반으로 쪼갠 지점 이상으로 넘어가면 정방향이나 역방향 중 둘 중 한곳으로 필연적으로 가까워지기 때문이다. 

 

j가 이동함에 따라 달라지는 시계 방향 거리에 주목해보자. 

j = 1 -> 1 

j = 2 -> 3

j = 3 -> 6

j = 4 -> 10 

 

이때, 4가 되는 순간 역방향보다 값이 커지면서 역방향이 답으로 선택되게 된다. 

 

따라서 시작점과 종료점을 선택할 때 절반 선택을 고려해서 작성한다. 

 

먼저 시작점(start)과 종료점(end), 그리고 현재까지 계산된 거리(currentDistance)와 최대 거리(maxDistance)를 저장할 변수들을 선언하자. 

 

int start = 0, end = 0;
int maxDistance = 0;
int currentDistance = 0;

 

 

이제 N개의 데이터에 대해서, 각 시작점(start)에 대한 반복문을 통해 최적의 종료점(end)를 찾는다. 

 

for (start = 0; start < N; start++) {
    while (end < start + N && currentDistance + distances[end % N] <= totalDistance / 2) {
        currentDistance += distances[end % N];
        end++;
    }

 

 

위의 반복문에서, while 루프는 종료점(end)를 이동시키면서, 현재 거리(currentDistance)와 다음 지점의 거리(distances[end % N])의 합이 전체 거리의 절반 이하가 되도록 유지한다. 왜 그럴까?  이 과정의 주 목적은 가장 멀리 떨어진 두 지점을 찾는 것이다. 원형 배열에서 두 지점 사이의 최대 거리는 전체 거리의 절반을 넘을 수 없기 때문이다. 앞에서 보았듯이, 이를 넘으면, 다른 방향으로 돌아가는 것이 더 짧은 거리가 되기 때문이다. 따라서, end 포인터를 이동시키면서 currentDistance가 전체 거리의 절반을 넘지 않도록 유지하는 것은, 시계 방향으로 갈 때 최대 거리를 찾기 위한 것이다.

 

이렇게 함으로써, 반시계 방향의 거리가 자동적으로 최소화된다. 즉 이제 반시계 방향의 거리가 자동적으로 최소화되었기 때문에, 계산된 시계 방향과 반시계 방향 거리 중 더 작은 값으로 최대 거리를 결정할 수 있게 된다. 

그 다음으로, 계산된 시계 방향과 반시계 방향의 거리 중 더 작은 값이 최대 거리를 결정한다.

 

int distanceClockwise = currentDistance;
int distanceCounterClockwise = totalDistance - distanceClockwise;

maxDistance = Math.max(maxDistance, Math.min(distanceClockwise, distanceCounterClockwise));

 

 

 

마지막으로, start 지점에서의 거리를 currentDistance에서 제거한다. 이렇게 하는 이유는 다음 start 지점에서의 탐색을 위해 currentDistance를 다시 초기화하기 위함이다.

 

     currentDistance -= distances[start];

 

 

투 포인터에서 이 부분이 중요한 부분 중에 하나이다. 왜 그럴까? 

 

모든 가능한 시작점에 대해 최적의 종료점을 찾기 위해서는 start 포인터를 하나씩 이동시키며 각 위치에서의 최적의 end 포인터 위치를 다시 찾아야 한다. 즉, start 포인터가 한 칸 이동할 때마다, currentDistance에서 이전 start 위치의 거리를 빼주어야 한다. 예를 들어, start가 0이고 end가 3인 상태에서 currentDistance는 0에서 3까지의 거리를 나타낸다. start를 1로 이동시킬 때, currentDistance에서 0과 1 사이의 거리(distances[start])를 빼주어야 새로운 start인 1에서 end까지의 거리가 표현되는 것이다. 이렇게 함으로써 모든 거리를 다시 계산하지 않고 중첩된 거리는 재사용하고 새롭게 설정된 범위를 계산할 수 있게 된다. 

 

 

💡 코드 구현

 

 

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {


   private static StringTokenizer receiveInput(BufferedReader bufferedReader) throws IOException {
      return new StringTokenizer(bufferedReader.readLine());
   }

   public static void main(String[] args) throws IOException {

      BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
      // BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));

      StringTokenizer stringTokenizer = receiveInput(bufferedReader);
      int N = parseInt(stringTokenizer.nextToken());

      int[] distances = new int[N * 2];
      int totalDistance = 0;
      for (int i = 0; i < N; i++) {
         distances[i] = Integer.parseInt(bufferedReader.readLine());
         distances[i + N] = distances[i]; // 환형 배열 처리
         totalDistance += distances[i];
      }

      int start = 0;
      end = 0;
      int maxDistance = 0;
      int currentDistance = 0;

      for (start = 0; start < N; start++) {
       // 종료점을 이동시키며 최적의 위치를 찾음
         while (end < start + N && currentDistance + distances[end % N] <= totalDistance / 2) {
            currentDistance += distances[end % N];
            end++;
         }

         int distanceClockwise = currentDistance;  // 시계 방향 거리
         int distanceCounterClockwise = totalDistance - distanceClockwise;

         maxDistance = Math.max(maxDistance, Math.min(distanceClockwise, distanceCounterClockwise));   // 최대 거리 업데이트

         currentDistance -= distances[start];  // 시작점을 이동시키며 거리 갱신
      }

      System.out.println(maxDistance);

   }

}