[SW Expert Academy] Intermediate / Array1 / 1206. [S/W 문제해결 기본] Flatten

Array1) 1204. Flatten_

package array1;

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

class Flatten {
	public static void main(String args[]) throws Exception {

		Scanner sc = new Scanner(System.in);
		// txt 파일 읽어오는 소스코드
		// System.setIn(new FileInputStream("res/1206_input.txt"));
		// 행, 열, 테스트케이스길이, 정답
		int dump;
		int Box[] = new int[100];

		// 10개의 테스트 케이스 반복
		for (int test_case = 1; test_case <= 10; test_case++) {
			dump = sc.nextInt();
			// 1.Box[]에 상자 높이 저장
			for (int i = 0; i < 100; i++) {
				Box[i] = sc.nextInt();
			}

			// 1-1.Box bubble sort를 이용하여 건물 높이대로 정렬
			int temp = 0;
			for (int i = Box.length - 1; i > 0; i--) {
				for (int j = 0; j < i; j++) {
					if (Box[j] > Box[j + 1]) {
						temp = Box[j];
						Box[j] = Box[j + 1];
						Box[j + 1] = temp;
					}
				}
			}
			// 2.dump만큼 평탄화 하기
			int i = 0;
			while(i != dump) {
				Box[99] -= 1;       //최대값 -1
				Box[0] += 1;        //최솟값 +1
				
				// 2-1. 가장 큰 수가 바꼈을 때(재 정렬)
				for (int j = 0; j < 100; j++) {
					if(Box[99-j]<Box[99-(j+1)]) {
						temp = Box[99-j];
						Box[99-j] = Box[99-(j+1)];
						Box[99-(j+1)] = temp;
					}
					else
						break;
				}
				// 2-2. 가장 작은 수가 바꼈을 때(재 정렬)
				for (int j = 0; j < 100; j++) {
					if(Box[j]>Box[j+1]) {
						temp = Box[j];
						Box[j] = Box[j+1];
						Box[j+1] = temp;
					}
					else 
						break;
				}		
				i++;
			}
			System.out.printf("#%d %d\n",test_case,Box[99]-Box[0]);
		}
	}
}

어려웠던 점

평탄화를 어떻게 시킬지에 대해서 고민을 많이 했다. 제일 높은 상자에서 제일 낮은 상자로 하나를 옮기면 되는 것이였다.

제일 높은 상자를 찾기 위해서는 결국 100개의 배열을 전부 돌아야 하기 때문에 bubble sort를 이용하여 박스 순서대로 높이를 정렬했다.

​

이렇게 되면 가장 낮은 박스는 index[0], 가장 높은 박스는 index[99]에 저장되어 있기 때문에 전체 배열을 돌지 않고도 높은 상자에서 낮은 상자로 쉽게 옮길 수가 있었다.

​

1. index[99]에서 index[0]으로 박스 하나를 옮겨주기 위해 index[99]-1, index[0]+1을 해주었다.

2. 상자를 옮김으로써 최소높이와 최대높이가 변경될 수 있기 때문에 2-1, 2-2의 반복문을 이용하여 항상 index[0]과 index[99]에 최대, 최소 높이가 오게 하였다.

3. 총 이동 횟수를 처음 입력받은 dump만큼 옮겨주었고 최고높이와 최소높이의 차이도 index[99]-index[0]으로 쉽게 구할 수 있었다.

 

풀고 나서 느낀점

처음에는 2차원 배열로 풀려고 했으나 브레인스토밍을 하던 중 1차원 배열로 충분히 풀 수 있을 것 같았다.

또한 최대한 반복문을 안쓰고 메모리낭비를 안하는 식으로 코딩을 하고 싶어서 내가 가지고 있는 지식 내에서 많은 고민을 했던 것 같다.

아직 bubble sort 알고리즘만 배운 상태라 어떤 알고리즘이 더 효율적인지는 구분을 못하지만 점점 더 공부하고 나서 더 효율적으로 코드를 짜도록 해야겠다.