이것저것 개발 블로그

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW8Wj7cqbY0DFAXN 

문제)

풀이)

이 문제는 조합으로 풀면 괜찮게 풀린다.

사실 조합코드를 짜기가 조금... 귀찮아서 어차피 2개만 뽑는 것이니 for문 2개를 이용해서 풀었다.

두 개의 간식을 더하고, 그것이 경계를 넘지 않으면서 최대값을 찾는 과정을 반복한다!

import java.util.Scanner;
//import java.io.FileInputStream;

class Solution_D3_9229_한빈이와SpotMart{
	public static void main(String args[]) throws Exception{
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			int N = sc.nextInt();
			int M = sc.nextInt();
			int[] snack = new int[N];
			for(int i=0; i<N; i++) {
				snack[i]=sc.nextInt();
			}
			
			int answer = 0;
			int temp = 0;
			
			
			for(int i=0; i<N-1; i++) {
				for(int j=i+1; j<N; j++) {
					temp = snack[i]+snack[j];
					if(temp<=M && answer<temp) {
						answer = temp;
					}
				}	 
			}
			
			if(answer == 0) {
				answer = -1;
			}
			
			
			System.out.println("#"+test_case + " " + answer);
			
		}
		sc.close();
	}
}

조합으로 짠 코드!!

시간은 더 오래 걸린다.

import java.util.Scanner;
//import java.io.FileInputStream;

class Solution_D3_9229_한빈이2{
	
	static int[] snack;
	static int N, M, answer;
	static boolean[] v;
	public static void comb(int start, int cnt) {
		if(cnt == 2) {
			cal();
			return;
		}
		
		for(int i=start; i<N; i++) {
			if(v[i])
				continue;
			
			v[i]=true;
			comb(i+1, cnt+1);
			v[i]=false;
			
		}
	}
	
	public static void cal() {
		int sum=0;
		for(int i=0; i<N; i++) {
			if(v[i])
				sum+=snack[i];
		}
		if(sum<=M)
			answer = Math.max(answer, sum);
	}
	
	public static void main(String args[]) throws Exception{
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			N = sc.nextInt();
			M = sc.nextInt();
			snack = new int[N];
			//과자 무게 기록 
			for(int i=0; i<N; i++) {
				snack[i]=sc.nextInt();
			}
			
			v=new boolean[N];
			answer = 0;
			comb(0, 0);
			
			if(answer == 0) {
				answer = -1;
			}
			
			System.out.println("#"+test_case + " " + answer);
			
		}
		sc.close();
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14w-rKAHACFAYD 

문제)

풀이)

LinkedList를 이용한다면 간단한 문제이다.

중간에 자주 추가가 이루어져서 linked list를 이용했다.

명령어를 만나고, start부터 end index 까지 삽입하는 방법을 사용했다.

그 후 완성되면 앞에서부터 10개 출력하면 끝!

//import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Scanner;


public class Solution_D3_1228_암호문1 {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++){
			int N = sc.nextInt();
			LinkedList<Integer> key = new LinkedList<>();
			for(int i=0; i<N; i++) {
				key.add(sc.nextInt());
			}

			int cmdNum = sc.nextInt();
			for(int i=0; i<cmdNum; i++) {
				String str = sc.next();
				int start = sc.nextInt();
				int end = sc.nextInt();
				for(int j=start; j<=start+end-1; j++) {
					key.add(j, sc.nextInt());
				}	
			}
			System.out.print("#"+test_case+ " ");
			for(int k=0; k<10; k++) {
				System.out.print(key.get(k) + " ");
			}
			System.out.println();
		}
		sc.close();
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14uWl6AF0CFAYD 

문제)

풀이)

Queue를 알고 있다면 간단한 문제다.

숫자를 큐에서 차례로 뽑으면서 1부터 5까지 빼고 다시 큐에 삽입하는 작업을 한다.

이때, 뺀 수가 0보다 같거나 작을 경우 0을 큐에 삽입한 후 종료한다.

//import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution_D3_1225_암호생성기 {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input2.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++){
			int t = sc.nextInt();
			Queue<Integer> queue = new LinkedList<>();
			for(int i=0; i<8; i++)
				queue.offer(sc.nextInt());
			
			int check = 0;
			int num = 1;
			while(true) {
				int pop_num = queue.poll();
				check = pop_num-num;
				
				if(check <= 0){
					check = 0;
					queue.offer(check);
					break;
				}
				
				queue.offer(check);
				num++;
				if(num == 6)
					num=1;
			}
			
			System.out.print("#"+test_case+" ");
			for(int j=0; j<8; j++) {
				System.out.print(queue.poll() + " ");
			}	
			System.out.println();
		}
		sc.close();
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq 

문제)

풀이)

아주 간단한 문제!

N크기도 작아서 for문으로 충분히 해결할 수 있다고 생각했다.

네모칸을 차례대로 움직이면서, 값을 모두 더한 후 비교하는 방식을 이용했는데,

범위만 주의하면 간단하다.

Python 코드

T = int(input())
for test_case in range(1, T + 1):
    n, m = map(int, input().split())
    matrix = []
    for _ in range(n):
        matrix.append(list(map(int, input().split())))

    answer = 0
    for i in range(n-m+1):
        for j in range(n-m+1):
            num = 0
            for row in range(m):
                for col in range(m):
                    num += matrix[row+i][col+j]
            if answer < num:
                answer = num
			           

    print('#{} {}'.format(test_case, answer))

JAVA 코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++)
		{
		int N = sc.nextInt();
			int M = sc.nextInt();
			int[][] matrix = new int[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			
			int answer = 0;
			for(int row=0; row<N-M+1; row++) {
				for(int col=0; col<N-M+1; col++) {
					int num=0;
					for(int i=0; i<M; i++) {
						for(int j=0; j<M; j++) {
							num += matrix[row+i][col+j];
						}
					}
					if(answer<num)
						answer=num;
				}
			}
			System.out.println("#"+test_case+" "+answer);

		}
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14eWb6AAkCFAYD 

문제)

풀이)

효율적이지는 않지만 정말 간단하게 생각했다.

짝이 알맞게 다 있다면 [, {, (, < 의 각각의 짝들이 다 있을거니까,

boolean 배열을 이용하여 각 괄호의 짝을 찾아주는 작업을 했다.

내가 푼 코드에 따르면 괄호의 위치와는 상관이 없다.

예를 들어, 코드에서 짝을 찾는 과정은 다음과 같다.

즉, 바깥쪽 <와 바깥쪽 >이 짝이 이루어지지 않는다는 것이다.

문제와의 의도와는 다르지만, 짝이 알맞게 있는지 없는지의 문제이므로 이렇게 풀어도 가능했다.

//import java.io.FileInputStream;
import java.util.Scanner;

public class Solution_D4_1218_괄호짝짓기 {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++)
		{
			int n = sc.nextInt();
			char[] arr = new char[n];	//input 배열
			boolean[] bool = new boolean[n];	//false
			String input = sc.next();
			arr = input.toCharArray();
			
			int answer = -1;
			for(int i=0; i<n; i++) {
				if(bool[i]==false) {	//탐색되지 않았으면
					switch(arr[i]) {
					case '{':{
						bool[i] = true;	//탐색
						for(int j=i+1; j<n; j++) {
							if(arr[j] == '}'&&bool[j]==false) {	//짝 찾고, 짝이 안 찾아진 애면
								bool[j]=true;
								break;
							}
						}
					}
						break;
					case '[':{
						bool[i] = true;
						for(int j=i+1; j<n; j++) {
							if(arr[j] == ']'&&bool[j]==false) {
								bool[j]=true;
								break;
							}
						}
					}
						break;
					
					case '<':{
						bool[i] = true;
						for(int j=i+1; j<n; j++) {
							if(arr[j] == '>'&&bool[j]==false) {
								bool[j]=true;
								break;
							}
						}
					}
						break;
					
					case '(':{
						bool[i] = true;
						for(int j=i+1; j<n; j++) {
							if(arr[j] == ')'&&bool[j]==false) {
								bool[j]=true;
								break;
							}
						}
					}
						break;
						
					}//switch
				}//if
			}//for
			for(int i=0; i<n; i++) {
				if(bool[i] == false) {	// 짝 없는애 있으면 0
					answer = 0;
					break;
				}
			}
			if(answer == -1)	//초기값 -1이니 0이 안 되었다는 것은 모두 짝이 있다는 것
				answer = 1;
			System.out.println("#"+test_case+" "+answer);
		}//test_case
		sc.close();
	}//main
}

이 문제의 정석은 stack을 활용하여 문제를 푸는 것이다.

입력값을 탐색하면서 여는 괄호를 만나면 stack에 저장하고, 닫는 괄호를 만나면 저장했던 괄호를 pop하여 잘 매칭되는지 확인한다.

이때, pop한 괄호와 닫는 괄호가 일치하지 않으면 틀렸으므로 0을 출력한다!

이 방식으로 문제를 푼다면 문제에서 원하는 방식으로 괄호 짝을 맞추면서 확인할 수 있다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Solution_D4_1218_괄호짝짓기 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		String opener = "<{([";//스택에 추가할 (시작)문자
		
		for (int tc = 1; tc <= 10; tc++) {
			
			int answer = 1;//기본값 1(유효)
			sb.append("#").append(tc).append(" ");
			
			int N = Integer.parseInt(br.readLine()); //괄호 개수
			String line = br.readLine(); 
			
			Stack<String> stack = new Stack<>(); //stack
			
			for (int i = 0; i < N; i++) {
				String item = line.substring(i, i + 1);  //괄호 하나
				
				if (opener.contains(item)) {//시작괄호 이면
					stack.push(item);
				} else {//끝괄호 이면
					boolean result = false;
					if (!stack.isEmpty()) {// 데이터가 있다면
						String prev = stack.pop();//스택의 끝에 저장된 시작괄호를 prev에 저장
						
						//끝괄호와 시작괄호 매칭 확인
						if (item.equals(">") && prev.equals("<")) {
							result = true;
						} else if (item.equals("]") && prev.equals("[")) {
							result = true;
						} else if (item.equals("}") && prev.equals("{")) {
							result = true;
						} else if (item.equals(")") && prev.equals("(")) {
							result = true;
						}
						
						if (!result) {// 안 맞음
							answer = 0; 
							break;
						}
					}
				}//끝괄호else
			}//for 입력N

			sb.append(answer).append("\n");
		}//tc
		System.out.println(sb);
	}//main
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB 

문제)

풀이)

백준에 나와있는 별찍기 문제와 비슷하게 풀이한다고 생각하면 좋다.

1. 합계를 구해야 하기 때문에 string으로 받은 것을 숫자로 변환하는 방법을 알아야 한다.

str.charAt(index) - '0';

위 코드를 수행한다면 string으로 받은 숫자들 중 index에 해당하는 숫자에 -'0'을 해주게 되어 int type의 숫자가 나온다!

2. 합계를 구하는 방법으로, 

N의 절반을 구한 후, 행 기준 위와 아래쪽을 나눠서 구한다.

이때, 정 가운데부터 차례로 행의 index만큼 늘려서 받으면

문제와 같이 가운데부터 점점 늘어나는 모양으로 더할 수 있다.

import java.util.Scanner;

public class Solution_D3_2805_농작물수확하기 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = sc.nextInt();
			int[][] farm = new int[N][N];
			
			
			for(int i=0; i<N; i++) {
				String str = sc.next();
				for(int j=0; j<str.length(); j++) {
                	//숫자 변환
					farm[i][j] = str.charAt(j)-'0';
				}
			}
			
			
			int answer = 0;
            //중간 위쪽
			for(int i=0; i<N/2; i++) {
				for(int j=N/2-i; j<=(N/2+i); j++) {
					answer += farm[i][j];
				}
			}
			
			//중간부터 아래쪽
			for(int i=N/2; i>=0; i--) {
				for(int j=N/2-i; j<=N/2+i; j++) {
					answer += farm[N-i-1][j];
				}
			}
			
			System.out.println("#"+test_case + " " + answer);
		}//test_case
		sc.close();
	}//main
}

이 문제는 절반으로 나누는건 잘했는데 열을 기준으로 절반에서 어떻게 계속 더할지를 헤맸다.

간단하게 규칙을 찾을 수 있었는데ㅠ 연습해야지!

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LyE7KD2ADFAXc 

문제)

풀이)

사실 어려운 문제는 아닌데, 구현해야 할 부분이 많다.

진짜 빡구현 문제!!

map 정보를 받은 이후, direction에 따라 dir이라는 인덱스를 초기화해준다.

또한 명령어에 따라 switch를 통해 명령을 수행한다.

이때, S명령어에서 dir에 따라 포탄을 쏘고, map에 따라 변경되는 것을 업데이트 해준다. 

코드가 길어서 좀 보기 어려울 수는 있지만, 구조 자체는 어렵지 않다.

전차가 움직이는 부분과 포탄을 쏘는 부분을 따로 함수로 만들면 더 깔끔하다!

import java.util.Scanner;
import java.io.FileInputStream;

public class Solution_D3_1873_상호의배틀필드 {

	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{
			
			int H = sc.nextInt();
			int W = sc.nextInt();
			char[][] map = new char[H][W];
			char direction = '*'; // 전차 방향
			int dir=-1; // 전차 방향 인덱스 
			int x=0, y=0;	//전차 위치
			// map 입력
			for(int i=0; i<H; i++) {
				String temp = sc.next();
				for(int j=0; j<W; j++) {
					map[i][j] = temp.charAt(j);
					if(map[i][j] == '^' || map[i][j] == 'v' || map[i][j] == '<' || map[i][j] == '>') {
						direction = map[i][j];
						x = i;
						y = j;
					}	
				}
			}
			switch(direction) {
				case '^':
					dir=0;
					break;
				case 'v':
					dir=1;
					break;
				case '<':
					dir=2;
					break;
				case '>':
					dir=3;
					break;
			}
			
			// 명령어 입력
			int N = sc.nextInt();
			char[] cmd = new char[N];
			String temp = sc.next();
			cmd = temp.toCharArray();
			
			// U D L R
			//char[] d = {'U', 'D', 'L', 'R', 'S'};
			int[] dx = {-1, 1, 0, 0}; // row
			int[] dy = {0, 0, -1, 1}; //col
			
			for(int i=0; i<N; i++) {
				char c = cmd[i];
				
				switch(c) {
					case 'U':{
						dir=0;
						map[x][y] = '^';
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						if(0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny] == '.') {
							map[nx][ny] = map[x][y];
							map[x][y]='.';
							x=nx;
							y=ny;
						}
						break;
					}
						
					case 'D':{
						dir=1;
						map[x][y] = 'v';
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						if(0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny] == '.') {
							map[nx][ny] = map[x][y];
							map[x][y]='.';
							x=nx;
							y=ny;
						}
						break;
					}
						
					case 'L':{
						dir=2;
						map[x][y] = '<';
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						if(0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny] == '.') {
							map[nx][ny] = map[x][y];
							map[x][y]='.';
							x=nx;
							y=ny;
						}
						break;
					}
						
					case 'R':{
						dir=3;
						map[x][y] = '>';
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						if(0<=nx && nx<H && 0<=ny && ny<W && map[nx][ny] == '.') {
							map[nx][ny] = map[x][y];
							map[x][y]='.';
							x=nx;
							y=ny;
						}
						break;
					}
						
					case 'S':
						int s_idx=0;
						switch(dir) {
							case 0://U
								s_idx = x;
								while(true) {
									if(s_idx-1<0 || map[s_idx-1][y]=='#')
										break;
									if(map[s_idx-1][y] == '*') {
										map[s_idx-1][y] = '.';
										break;
									}
									s_idx--;
								}
								break;

							case 1:
								s_idx = x;
								while(true) {
									if(s_idx+1>=H || map[s_idx+1][y]=='#')
										break;
									if(map[s_idx+1][y] == '*') {
										map[s_idx+1][y] = '.';
										break;
									}
									s_idx++;
								}
								break;
								
							case 2:
								s_idx = y;
								while(true) {
									if(s_idx-1<0 || map[x][s_idx-1]=='#')
										break;
									if(map[x][s_idx-1] == '*') {
										map[x][s_idx-1] = '.';
										break;
									}
									s_idx--;
								}
								break;
								
							case 3:
								s_idx = y;
								while(true) {
									if(s_idx+1>=W || map[x][s_idx+1]=='#')
										break;
									if(map[x][s_idx+1] == '*') {
										map[x][s_idx+1] = '.';
										break;
									}
									s_idx++;
								}
								break;
						}//case S
						break;
				}//switch
				
			}//cmd
			
			//출력
			System.out.print("#"+test_case+" ");
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					System.out.print(map[i][j]);
				}
				System.out.println();
			}
			
		
		}//test_case
		sc.close();
	}//main
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq 

문제)

풀이)

이 문제는 방향을 바꾸는데 신경을 조금 쓰면 해결되는 문제다.

먼저, 시계방향으로 계속 회전하며 전진하므로 오른쪽, 아래, 왼쪽, 위를 반복하면서 간다.

따라서, 해당 방향을 유지하다 index가 map 범위 밖으로 나가거나, map에 숫자가 채워져 있으면 방향을 바꾸면 된다.

또한 숫자는 입력받은 n의 제곱만큼의 숫자가 채워지므로, whlie문 탈출 조건을 이것으로 정했다.

import java.util.Scanner;

public class Solution_D2_1954_달팽이숫자 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++){
			int n = sc.nextInt();
			int[][] map = new int[n][n];
			int num = 1;
			// right, down, left, up
			int[] dx= {0,1,0,-1};
			int[] dy= {1,0,-1,0};
			int idx=0;
			int x=0;
			int y=0;
			
			while (num<=n*n) {	// 숫자를 다 채울 때까지
                //map 범위 내인가? 맞으면 채우고, 다음 곳으로
				if(0<=x && x<n && 0<=y && y<n && map[x][y]==0) { 				
                	map[x][y] = num;
					x += dx[idx%4];
					y += dy[idx%4];
					num++;
				}
				else {
					//범위 내가 아닐 때, 한 칸 더 계산되었으므로 원상태 복구 
					x -= dx[idx%4];
					y -= dy[idx%4];
                    //방향 틀기
					idx+=1;
					x += dx[idx%4];
					y += dy[idx%4];
				}
					
			}//while
			
			
			System.out.println("#"+test_case);
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					System.out.print(map[i][j]+" ");
				}
				System.out.println();
				
			}	
		}//test_case
		sc.close();
	}//main
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh 

문제)

풀이)

이 문제는 목적지에서 거꾸로 원하는 장소를 찾아가면 된다!

즉, 아래에서 위로 올라가므로 행의 값은 -1을 계속 해주고, 왼쪽 또는 오른쪽에 길이 있으면 전체 범위 내에서 길이 있을 때까지 반복해서 전진한다.

이때, 내 코드에서는 이미 한 번 더 더했으므로, 빼주는 작업이 필요하다!

마지막으로, 행인 x의 값이 0이면 끝났으므로 탈출!

y값을 출력해주면 답이다.

//import java.io.FileInputStream;
import java.util.Scanner;

public class Solution_D4_1210_Ladder1 {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input2.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++)
		{
			int tc = sc.nextInt();
			int x=0;
			int y=0;
			int[][] ladder = new int[100][100];
			for(int i=0; i<100; i++) {
				for(int j=0; j<100; j++) {
					ladder[i][j] = sc.nextInt();
					if (ladder[i][j] == 2) {
						x=i;
						y=j;
					}
				}
			}
			
			// 좌, 우
			int[] dx= {0, 0};
			int[] dy= {-1, 1};
			int nx=0;
			int ny=0;
			while(true) {
				//전진
				x -= 1;
				//y=y;
				
				//좌, 우 살피기
				for(int i=0; i<2; i++) {
					nx = x + dx[i];
					ny = y + dy[i];
					
					if(0<=nx && nx<100 && 0<=ny && ny<100 && ladder[nx][ny]==1) {
						while(0<=nx && nx<100 && 0<=ny && ny<100 &&ladder[nx][ny]==1) {
							nx += dx[i];
							ny += dy[i];
						}
						//한 칸 더 갔으므로 빼주기
						x=nx-dx[i];
						y=ny-dy[i];
						break;
					}
				}
				
				if(x==0)	//맨 위므로 정답 찾았다!
					break;
			}
			System.out.println("#"+test_case+ " "+y);		
		}
		sc.close();
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh 

문제)

풀이)

이 문제는 말 그래도 평탄했다.

다만 좀 오래 걸렸던 부분이 있었는데, 그냥 dumpNum 줄여가면서 하나씩 빼면 되는데 괜히 횟수 줄여보겠다고 옆자리 애랑 비교하고 난리났다.

어차피 sort하면 작은 애가 앞으로 올 것이고, 같은애가 여러개 있더라도 더해지면 다시 작은 애가 앞으로 올 것인데 그걸 생각 못했다.

어쨌든, 정렬을 통해 오름차순으로 줄세워두고, 맨 뒤에서 하나를 빼 맨 앞으로 넘기는 작업을 반복했다.

그리고, flatten 됨을 확인까지 한다면, 쓸데없이 빼는 작업을 줄일 수 있다!

확인하는 작업은, 정렬 후 맨 앞과 맨 끝의 높이 차이가 0 또는 1인지만 확인하면 된다.

//import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Solution_D3_1208_Flatten {

	public static void main(String[] args) throws FileNotFoundException {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++){
			int dumpNum = sc.nextInt();
			int[] arr = new int[100];
			for(int i=0; i<100; i++) {
				arr[i]=sc.nextInt();
			}
			
			Arrays.sort(arr);
			while(dumpNum>0) {
				if(arr[99]-arr[0]==0 || arr[99]-arr[0]==1)
					break;
				arr[99]-=1;
				arr[0]+=1;
				dumpNum--;
				Arrays.sort(arr);
			}
			int answer = arr[99]-arr[0];
			
			System.out.println("#"+test_case+" "+answer);
		}
		sc.close();
	}

}