[SWEA] JAVA - 1208.Flatten

전에 이와 비슷한 문제를 풀어서 정렬을 사용해 금방 풀수있었다.

평탄화의 핵심 아이디어는 가장 큰값과 가장 작은 값의 차이를 계속 상쇄시키는것인데 이때 가장 큰값의 값을 하나씩 빼서 가장 작은값에게 하나씩 더해주면 된다.

 

나는 주어진 배열을 내림차순으로 정렬시켜줬다.(오름차순도 상관없다 주어진 문제 상황을 그대로 재현하려고해서 내림차순으로 정렬시켜줬다.) 그 다음으로 dump 횟수 만큼 가장 큰 값을 가진 첫번째 원소에서 1을 빼준 다음 가장 작은 원소인 마지막원소에 1을 더해줬다.

 

(Arrays.sort의 시간복잡도는 O(nlogn) 이고 주어진 테스트케이스가 10개로 고정되있기 때문에 Arrays.sort 메소드를 사용하여 풀었다)

 

public static void solve2() throws IOException {
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

  for (int t = 1; t <= 10; t++) {
    int dumpCnt = Integer.parseInt(in.readLine());
    Integer[] height = new Integer[100];
    StringTokenizer st = new StringTokenizer(in.readLine(), " ");
    for (int i = 0; i < 100; i++) {
    	height[i] = Integer.parseInt(st.nextToken());
    }

    //solve
    Arrays.sort(height, Collections.reverseOrder());//내림차순
    while(dumpCnt-- > 0) {
      --height[0];
      ++height[99];
      Arrays.sort(height, Collections.reverseOrder());//내림차순
    }

    System.out.println("#"+t+" "+(height[0]-height[99]));
  }
}