[SWEA 1208 / d3 / 그리디 / Java] Flatten

그리디 문제이다.

해당 문제는 순서와 상관없이 제일 높은 층을 가지고 있는 상자를 제일 낮은 층을 가지고 있는 층에 하나씩 올려주면 된다. 

Java 기준 시간은 20초가 주어졌고, 덤프 횟수 만큼 오름차순으로 정렬을 하기 위해선 시간 복잡도를 확인해야한다. 

 

sort 의 시간 복잡도는 O(nlogn) 이며 덤프의 횟수는 최대 1000인 것을 감안한다면 

* n = 배열의 크기 = 100

 

1000*(100long100)   =  약 700,000 연산

1억번의 연산이 1초라는 것을 감안하면  제한 시간 20초는 여유롭다. 

 

#접근 방법 

1. 오름차순 정렬 

2. 시작 배열과 끝 배열 값을 ++, -- 

3. 반복

 

* 시작과 끝 값이 같다면 평탄화 완료되었기 때문에 루프 빠져나와라

import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		int T=10;
		int [] arr = new int[101]; 
	
	for(int test_case = 1; test_case <= T; test_case++)
	{
		
	    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n= Integer.parseInt(in.readLine());
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		for(int i=0; i<100; i++) {
			arr[i+1] = Integer.parseInt(st.nextToken()); 
		}
		
		for(int i=0; i<n ; i++) {
			Arrays.sort(arr);
			if(arr[100]==arr[1])break; 
			arr[1]++; 
			arr[100]--; 
		}
		Arrays.sort(arr);
		System.out.printf("#%d %d%n", test_case, arr[100]-arr[1]);
	}
  }
}

SW Expert Academy