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

* 출처: SWEA swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh&categoryId=AV139KOaABgCFAYh&categoryType=CODE&problemTitle=1208&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

내 생각

 

1. 첫번째 풀이

높이가 가장 높은 곳과 낮은 곳의 좌표를 구하도록 findMaxIdx(), findMinIdx() 메소드를 작성했다.

이후, dump() 메소드를 만들어서 높은 곳에서 낮은 곳으로 dump할 수 있도록 했다.

이렇게 푸니까 답은 나오지만, 시간이 오래 걸린다는 단점이 있다.

 

public class SWEA1208_1 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder("");

		int T = 10; // 테스트케이스 수
		for (int i = 0; i < T; i++) {
			boolean[][] matrix = new boolean[100][100];
			int dumpNum = Integer.parseInt(in.readLine()); // 덤프 횟수
			st = new StringTokenizer(in.readLine(), " "); // 높이 입력
			// matrix 초기화
			for (int j = 0; j < 100; j++) { // 높이 100개 입력
				int height = Integer.parseInt(st.nextToken());
				for (int k = 0; k < height; k++) {
					matrix[k][j] = true;

				}
			}
			for (int k = 0; k < dumpNum; k++) {
				dump(matrix);
			}
			int ans = heightDiff(matrix);
			sb.append("#").append(i + 1).append(" ").append(ans).append('\n');
		}
		System.out.println(sb);

	}

	static int heightDiff(boolean[][] matrix) {
		int[] maxXY = findMaxIdx(matrix);
		int[] minXY = findMinIdx(matrix);
		int ans = maxXY[0] - minXY[0];
		return ans;
	}

	static void dump(boolean[][] matrix) {
		int[] maxXY = findMaxIdx(matrix);
		int[] minXY = findMinIdx(matrix);

		matrix[maxXY[0]][maxXY[1]] = false;
		if (minXY[0] + 1 == 100)
			return;
		matrix[minXY[0] + 1][minXY[1]] = true;
	}

	static int[] findMaxIdx(boolean[][] matrix) {
		int maxI = 0;
		int[] xy = new int[2];
		for (int j = 0; j < 100; j++) {
			int tmpI = 0;
			for (int i = 0; i < 100; i++) {
				if (matrix[i][j] == true) {
					if (maxI < i) {
						maxI = i;
						xy[0] = i;
						xy[1] = j;
					}
				}
			}
		}
		return xy;
	}

	static int[] findMinIdx(boolean[][] matrix) {
		int minI = 100;
		int[] xy = new int[2];

		for (int j = 0; j < 100; j++) {
			int tmpI = minI;
			for (int i = 0; i < 100; i++) {
				if (matrix[i][j] == false) {
					tmpI = i - 1;
					break;
				}
			}
			if (minI > tmpI) {
				minI = tmpI;
				xy[0] = minI;
				xy[1] = j;
			}
		}

		return xy;
	}
}

 

2. 두번째 풀이

어차피 100개의 열이 있으므로, 높이만 담을 1차원 배열만 만들면 된다.

이 배열을 계속 정렬하면서, 최소와 최대 높이를 dump해주면 된다.

public class SWEA1208_2 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder("");

		int T = 10; // 테스트케이스 수
		for (int i = 0; i < T; i++) {
			int[] matrix = new int[100];	// 높이 담을 배열
			int dump = Integer.parseInt(in.readLine()); // 덤프 횟수
			int ans = 0;
			st = new StringTokenizer(in.readLine(), " "); // 높이 입력
			// matrix 초기화
			for (int j = 0; j < 100; j++) { // 높이 100개 입력
				int height = Integer.parseInt(st.nextToken());
				matrix[j] = height;
			}
			Arrays.sort(matrix);// 높이 정렬
			
			for(int j=0;j<dump;j++) {
				matrix[0]++;		// 최소 높이 
				matrix[99]--;		//최장 높이
				Arrays.sort(matrix);// 정렬
			}
			
			ans = matrix[99]-matrix[0];
			
			sb.append("#").append(i + 1).append(" ").append(ans).append('\n');
		}
		System.out.println(sb);
	}
}