1208 Flatten

URL

내 풀이

import java.util.*;
import java.io.*;
 
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int t = 1; t <= 10; t++) {
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] arr = new int[100];
            for (int i = 0; i < 100; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr);
             
            int idx1 = 1;
            int idx2 = 1;
            //뒤에서
             
            while (N > 0) {
                for (int i = 0; i < 100; i++) {
                    if (arr[99] > arr[99-idx1]) {
                        arr[99]--;
                        break;
                    }
 
                    if (arr[99] == arr[99-idx1]) {
                        idx1++;
                        if (arr[99] > arr[99-idx1]) {
                            arr[99-idx1+1]--;
                            break;
                        }
                    }
                }
 
                for (int i = 0; i < 100; i++) {
                    if (arr[0] < arr[0+idx2]) {
                        arr[0]++;
                        break;
                    }
 
                    if (arr[0] == arr[0+idx2]) {
                        idx2++;
                        if (arr[0] < arr[0+idx2]) {
                            arr[0+idx2-1]++;
                            break;
                        }
                    }
                }
                idx1 = 1; idx2 = 1;
                N--;
            }
            int result = arr[99] - arr[0];
            System.out.println("#" + t + " " + result);
        }
    }
}

풀이 방식

1. 먼저 arr에 값을 다 담는다.

2. 오름차순으로 정렬한다.

3. 인덱스끼리 크기를 비교하기 위해 작은수를 찾을 idx1 큰 수를 찾을 idx2변수 2개를 생성

4. 먼저 가장 큰 값이 arr[99] 번째부터 돌며 -1번째 인덱스보다 크다면 가장 큰 값 -1해 주고 만약 값이 같을 경우엔 가장 작은 인덱스를 -1 해준다.

5. 가장 작은수도 마찬가지.

6. 이렇게 하면 가장 큰 값이 항상 큰 상태를 유지하고 가장 작은 값이 항상 작은 상태를 유지하면 반복할 수 있다.

Solution

import java.io.*;
import java.util.*;
 
public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int t = 1; t <= 10; t++) {
            int dump = Integer.parseInt(br.readLine());
 
            int[] arr = new int[100];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 100; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
 
            for (int i = 0; i < dump; i++) {
                Arrays.sort(arr);
                arr[0]++;
                arr[99]--;
            }
            Arrays.sort(arr);
            int result = arr[99] - arr[0];
            System.out.println("#" + t + " " + result);
        }
    }
}

배운점

Solution의 방식은 아주 간단하게 매번 정렬을 해 주는 방식이다.
이 방식을 알고는 있었지만 매번 반복 해 주는것은 너무 비효율적인 방식인것 같아서
다른 방식을 생각 해 푼 것이다.

두 코드의 차이는 이정도인데... 흠... 별로 큰 차이는 아니지만 개선 했다.