[SWEA] 행렬찾기

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

행렬은 0이 아닌 수로 이루어져 있으므로 while문 두개로 행렬의 x좌표와 y좌표를 찾는다.

그 후, 행과 열을 곱한 값으로, 크기가 작은 순서대로 출력해야하므로 matrix 객체를 만들어 정렬해준뒤 출력한다.

JAVA Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Solution {
	static int[][] map;
	static int N;
	static ArrayList<matrix> m;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			map = new int[N + 1][N + 1];
			m = new ArrayList<>();
			for (int i = 1; i < N + 1; i++) {
				for (int j = 1; j < N + 1; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			for (int i = 1; i < N + 1; i++) {
				for (int j = 1; j < N + 1; j++) {
					int y = i;
					int x = j;
					if (map[i][j] != 0) {
						while (x+1<N+1 && map[y][x+1] != 0) {
							x = x + 1;
						}
						while (y+1<N+1 && map[y+1][x] != 0) {
							y = y + 1;
						}
						if (x - j + y - i > 0 ) {
							m.add(new matrix(x - j + 1, y - i + 1, (x - j + 1) * (y - i + 1)));
							
							for (int k = i; k < y + 1; k++) {
								for (int l = j; l < x + 1; l++) {
									map[k][l] = 0;
								}
							}
						}
					}
				}
			}
			Collections.sort(m, new Comparator<matrix>() {
				@Override
				public int compare(matrix o1, matrix o2) {
					if ( o1.RC > o2.RC ) { 
						return 1;
					} else {
						return -1;
					}
				}
			});
			
			System.out.print("#"+tc+" "+m.size());
			for(int i=0; i<m.size(); i++) {
				System.out.print(" "+m.get(i).C+" "+m.get(i).R);
			}
			System.out.println();
		}
	}

	public static class matrix {
		int R;
		int C;
		int RC;

		public matrix(int r, int c, int rc) {
			R = r;
			C = c;
			RC = rc;
		}
	}
}