[백준 - 13719번] Nizin - Java

문제 링크

https://www.acmicpc.net/problem/13719

문제

티어: 골드 2
알고리즘: 그리디, 애드 혹, 두 포인터

입력

첫 번째 줄에 배열의 요소 개수를 나타내는 정수 N (1 ≤ N ≤ 10^6)이 주어집니다.
두 번째 줄에는 N개의 공백으로 구분된 양의 정수들이 배열 A의 요소들로 주어집니다. 입력되는 숫자는 최대 10^9입니다.

출력

주어진 규칙에 따라 원래 배열을 팰린드롬으로 만드는 데 필요한 최소 이동 횟수를 출력하세요.

풀이

원래 배열을 팰린드롬으로 만들기 위해 최소 몇 번의 이동이 필요한지 출력해야 한다.

팰린드롬을 만들려면 결국 양쪽 수를 같게 해줘야 하는데, 세가지 경우로 나눌 수 있다.

• 이미 양쪽 수가 같다면 당연히 이동할 필요가 없다. 그래서 leftPoint는 +1 rightPoint는 -1 해준다.

• 양쪽 수가 다르다면 이동은 필수다.

  • 왼쪽 수가 더 크다면 오른쪽 수를 이동해야 한다.
  • 오른쪽 수가 더 크다면 왼쪽 수를 이동해야 한다. (이동은 덧셈이기 때문에 당연히 작은 쪽을 이동해야 됨)

이 경우로 구분하고 이동해 주면 어느 순간 lp >= rp 되는데 이때가 팰린드롬이 만들어진 시점이고, 총 이동 횟수는 최소가 된다. (필요할 때만 이동 했기 때문에)

이 풀이의 시간 복잡도는 O(N)이다.

소스 코드

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

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[] arr = new long[N];
      
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=0; i<N; i++) {
          arr[i] = Long.parseLong(st.nextToken());
      }
      
      int lp = 0;
      int rp = N - 1;
      int cnt = 0;
      while(lp < rp) {
          if(arr[lp] == arr[rp]) {
              lp += 1;
              rp -= 1;
          } else if(arr[lp] > arr[rp]) {
              arr[rp - 1] += arr[rp];
              rp -= 1;
              cnt += 1;
          } else if(arr[lp] < arr[rp]) {
              arr[lp + 1] += arr[lp];
              lp += 1;
              cnt += 1;
          }
      }
      
      System.out.println(cnt);
  }
}