[백준 - 27727번] 버튼 정렬 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 애드 혹
길이가 $N$인 수열 $A$와 버튼이 있다.

버튼을 누를 때마다 $A$에서 가장 작은 값을 갖는 원소를 하나 선택하여 $1$을 더한다. 그러한 원소가 여러 개라면 그 중 가장 앞에 있는 원소를 선택한다.

입력

첫째 줄에 수열의 길이 $N(1 \leq N \leq 100\,000)$이 주어진다.

둘째 줄에 수열의 원소 $A_i(1 \leq A_i \leq 10^9)$가 공백을 사이에 두고 순서대로 주어진다.

셋째 줄에 버튼을 누른 횟수 $K(1 \leq K \leq 10^{18})$가 주어진다.

주어지는 입력은 모두 정수다.

출력

첫째 줄에 버튼을 $K$번 누르는 동안 $A$가 비내림차순으로 정렬된 횟수를 출력한다.

버튼을 한 번도 누르지 않았을 때 수열이 정렬된 경우는 횟수에 포함하지 않는다.

풀이

K번 누르는 동안 A가 오름차순으로 정렬된 횟수를 출력한다.

단순히 생각했을 때 버튼 누르고, 수열 조작하고를 반복할 수 있다. 하지만 K는 최대 10^18이기 때문에 당연히 불가능하다.

이 문제에는 중요한 특징이 있다. 만약 수열에서 가장 큰 값이 마지막이 아닌 위치에 존재한다면 이 수열을 오름차순 정렬하기 위해서 몇 번 눌러야 할까?

모든 값을 가장 큰 값으로 맞춰줘야 하기 때문에 모든 값을 돌면서 가장 큰 값에서 해당 값을 뺀 값의 합이 된다. ex) 1 4 3 -> 4 - 1 + 4 - 3

앞의 과정을 거치면 모든 값이 같아지게 되는데 ex) 4 4 4
N의 길이만큼 눌러야 오름차순 정렬되기 때문에 간단한 공식으로 구할 수 있다. K / N

이를 일반화한다면, 1 3 2 10와 같은 경우도 다르지 않다는 것을 알 수 있다.
이 경우 4는 제대로 위치하지만 3이 제대로 위치하지 않는다. 그렇기 때문에 1과 2를 3으로 맞춰줘야 한다. 이때 첫 번째로 오름차순 정렬을 하고, 이후에는 3 3 3 10이 되는데,
첫 번째 오름차순 정렬되고 난 후에는 간단한 공식만으로 몇 번 눌렀는지 알 수 있다.

3보다 큰 수는 10이기 때문에 3 3 3 10 -> 10 10 10 10으로 정렬하는데 누른 횟수는 3 * (10 - 3)이 된다. 그리고 그 과정에서 오름차순으로 정렬되는 횟수는 10 - 3이 된다.

만약 주어진 K로 10 10 10 10을 만드는게 불가능하다면 (curK + cnt > K) 답에 K / 3을 더해주면 된다. 어차피 10보다 큰 수는 나타날 수 없기 때문이다.

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

소스 코드

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

class Node implements Comparable<Node> {
    int ind; 
    long num;
    Node(int ind, long num) {
        this.ind = ind;
        this.num = num;
    }
    
    @Override
    public int compareTo(Node o) {
        if(this.num < o.num) {
            return -1;
        } else if(this.num > o.num) {
            return 1;
        } else {
            if(this.ind < o.ind) {
                return -1;
            } else if(this.ind > o.ind) {
                return 1;
            }
        }
        return 0;
    }
}

public class Main {
    static int N;
    static long K;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      
      Node[] A = new Node[N];
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=0; i<N; i++) {
          A[i] = new Node(i, Long.parseLong(st.nextToken()));
      }
      Arrays.sort(A);
      K = Long.parseLong(br.readLine());
      if(N == 1) {
          System.out.println(K);
          return;
      }
      long curK = 0;
      long asc = 0;
      int startInd = 1;
      for(int i=N-1; i>=2; i--) {
          if(A[i].ind != i) {
              startInd = i;
              break;
          }
      }
      
      for(int i=0; i<startInd; i++) {
          curK += A[startInd].num - A[i].num;
          if(curK > K) {
              System.out.println(asc);
              return;
          }
      }
      if(curK > 0) {
          asc += 1;
      }
      int nextInd = startInd + 1;
      while(nextInd < N) {
          if(A[nextInd - 1].num != A[nextInd].num) {
              long cnt = nextInd * (A[nextInd].num - A[nextInd - 1].num);
              if(curK + cnt > K) {
                  break;
              }
              curK += cnt;
              asc += A[nextInd].num - A[nextInd - 1].num;
          }
          nextInd += 1;
      }
      
      asc +=  (K - curK) / (long) nextInd;
      System.out.println(asc);
  }
}