[SWEA] 1208. [S/W 문제해결 기본] 1일차 - Flatten (D3) - java

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

접근법

알고리즘은 문제에서 말해주는 그대로 100개의 숫자 중 가장 큰 수와 가장 작은 수를 가져와 가장 큰 수는 -1, 가장 작은 수는 +1 해주면 된다. 가장 작은 수와 큰 수를 쉽게 가져오기 위해 배열은 항상 정렬된 상태여야 한다.

시간 제한이 20초라 덤프 -> Arrays.sort()를 반복해도 문제가 없을 듯 한데, 나는 배열의 양 끝에서만 이동이 주로 발생하지 않을까? 싶어서 양 끝에서 반복문을 사용해 정렬해주었다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        for (int t = 1; t <= 10; t++) {
            int n = 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());
            }
 
            Arrays.sort(arr);
 
            for (int i = 0; i < n; i++) {
                // 평탄화가 완료된 경우
                if (arr[99] - arr[0] <= 1) {
                    break;
                }
 
                arr[0]++;
                arr[99]--;
 
                // 앞 정렬
                for (int j = 1; j < 100; j++) {
                    if (arr[j] >= arr[j - 1]) {
                        break;
                    }
 
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                }
 
                // 뒤 정렬
                for (int j = 98; j >= 0; j--) {
                    if (arr[j] <= arr[j + 1]) {
                        break;
                    }
 
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
 
            sb.append('#').append(t).append(' ').append(arr[99] - arr[0]).append('\n');
        }
 
        System.out.println(sb);
    }
}