BOJ - 17140 이차원 배열과 연산

17140 이차원 배열과 연산 : https://www.acmicpc.net/problem/17140

---

Problem

---

Solve

R연산과 C연산만 조건에 맞게 구현해주면 풀수있는 문제이다.

각 연산은 (1)각각의 수가 몇번의 수가 나왔는지 알아야한다, (2)수의 등장 횟수가 커지는 순으로, (3)그러한 것들이 여러가지면 수가 커지는 순으로 정렬한다.

1. 행 또는 열에서 각 수가 몇번 나왔는지 Map에 저장한다.
2. 해당 수와 개수를 담고있는 Number객체를 List에 저장한다. 그 후 정렬을 통해 등장 횟수가 커지는 순으로
3. 여러가지일 경우 해당 수가 커지는 순으로 정렬되게 설정한다.

위의 방법을 각 초마다 조건에 맞는 연산을 수행한다.
A[r][c]의 값이 k인 경우 반복을 멈추고 값을 반환한다.

그리고 배열의 크기가 100을 넘어가는 경우 처음 100개를 제외하고 버린다는 조건도 명심하면서 구현하자.
(연산으로 갱신되는 행,열의 크기가 100을 넘지 않도록 조건을 걸어서 구현)

---

Code

public class 이차원배열과연산 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int[][] A = new int[100][100];
		for (int i = 0; i < 3; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 3; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		//초기 배열 크기 3*3
		int R = 3;
		int C = 3;
		int answer = -1;

		//100초를 넘어가면 -1 반환
		for (int time = 0; time <= 100; time++) {
        	//A[r-1][c-1]의 값이 k일 경우 걸린 시간 반환(구현한 배열은 (0,0)부터 시작한다.)
			if (A[r - 1][c - 1] == k) {
				answer = time;
				break;
			}

			//R연산 조건
			if (R >= C) {
            	//연산 후의 갱신될 값들의 배열
				int[][] copyA = new int[100][100];
				for (int i = 0; i < R; i++) {
                	//행에서 각각 수의 개수를 저장
					HashMap<Integer, Integer> numMap = new HashMap<>();
                    //정렬을 위한 list
					List<Number> rowList = new ArrayList<>();
                    //최대 100까지의 수만 연산
                    //C가 100보다 작다면 C까지만 연산
					for (int j = 0; j < 100 && j < C; j++) {
                    	//R연산에서는 다른 row의 열이 길다면 열의 길이가 짧은 row의 남는 자리는 0
						if (A[i][j] == 0)
							continue;
						//0이 아니라면 해당 수의 개수 갱신
						numMap.put(A[i][j], numMap.getOrDefault(A[i][j], 0) + 1);
					}

					//정렬을 위한 list에 Number추가
					for (Integer key : numMap.keySet()) {
						rowList.add(new Number(key, numMap.get(key)));
					}
                    //정렬
					Collections.sort(rowList);

					int idx = 0;
                    //각각의 수는 해당 수와 개수, 총 2개의 값을 넣어야한다.
                    //최대 길이 100까지의 값만 넣는다.
					for (int n = 0; n < 100 && n < rowList.size() * 2; n++) {
                    	//해당 수 추가
						copyA[i][n] = rowList.get(idx).num;
                        //열의 다음 index(배열에 갱신할 열 위치)
						n++;
                        //해당 수의 개수 추가
						copyA[i][n] = rowList.get(idx).count;
                        //list의 다음 index(수)
						idx++;
					}

					//R연산된 값과 열의 크기를 비교(연산된 열의 크기가 기존 열보다 크다면 연산된 열의 크기 중 가장 큰 값을 갱신)
                    //열의 크기가 100을 넘는다면 최대 열의 크기는 100
					C = Math.max(C, Math.min(rowList.size() * 2, 100));
				}
                //연산으로 갱신된 배열 갱신
				A = copyA;

			} else {
            //C연산 조건
            //R연산과 행,열 참조빼고 동일
				int[][] copyA = new int[100][100];
				for (int i = 0; i < C; i++) {
					HashMap<Integer, Integer> numMap = new HashMap<>();
					List<Number> colList = new ArrayList<>();
					for (int j = 0; j < R; j++) {
						if (A[j][i] == 0)
							continue;

						numMap.put(A[j][i], numMap.getOrDefault(A[j][i], 0) + 1);
					}

					for (Integer key : numMap.keySet()) {
						colList.add(new Number(key, numMap.get(key)));
					}
					Collections.sort(colList);

					int idx = 0;
					for (int n = 0; n < 100 & n < colList.size() * 2; n++) {
						copyA[n][i] = colList.get(idx).num;
						n++;
						copyA[n][i] = colList.get(idx).count;
						idx++;
					}

					R = Math.max(R, Math.min(colList.size() * 2, 100));
				}
				A = copyA;
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static class Number implements Comparable<Number> {
		int num;
		int count;

		public Number(int num, int count) {
			this.num = num;
			this.count = count;
		}

		@Override
		public int compareTo(Number o) {
			int result = this.count - o.count;
			if (result == 0) {
				result = this.num - o.num;
			}

			return result;
		}
	}
}

---

Result

1초마다 각 연산을 조건에 따라 수행해줘야하는데 문제를 잘못 이해해서 조건에 부합하면 시간을 지났는데 연산을 수행하지 않도록 구현해서 시간을 많이 잡아먹었다.. 예외케이스도 어느정도 생각하면서 구현하자..
알고리즘은 국어시험..

---

Reference