[SWEA] 1208. Flatten

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

SW Expert Academy

---

접근 방법

sort 하여 최대 최소를 구하고

조건이 맞을 때 수를 빼고 더해 줬다.

다음 차례의 수와 높이가 같거나 1이상 차이가 나면

시작 지점으로 이동하여 min or max 를 갱신하고 다시 반복하게 하였다.

처음부터 끝까지 sort 하며 해결하는 것보다는 1000 kb, 10 ms 정도가 나았다.

 

소스 코드

import java.util.*;
import java.io.*;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = 10;
         
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int b_length = 100;
            int N = Integer.valueOf(br.readLine());
            int[] b = new int[b_length];
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int i=0; i<b_length; i++)
                b[i] = Integer.valueOf(st.nextToken());
             
            Arrays.sort(b);
             
            int i=0, j=b_length-1;
            int min=b[i], max=b[j];
            while(N>0) {
                if(b[i] > b[i+1]) ++i;
                ++b[i];
                if(i>0 && (b[i] == b[i+1] ||b[i+1]-b[i] >= 1)) { min = b[i]; i = 0; }
                 
                if(b[j] < b[j-1]) --j;
                --b[j];
                if(j<b_length-1 && (b[j] == b[j-1] || b[j]-b[j-1] >= 1)) {max = b[j]; j = b_length-1;}
                 
                --N;
            }
            System.out.println("#" + test_case + " " + (max - min));
        }
    }
}