[백준] 17140. 이차원 배열과 연산 - 골드4

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

문제 설명

크기가 3X3인 배열이 주어진다. 1초가 지날 때마다 이 배열에 대해 연산을 하는데, 연산은 다음과 같이 두 가지다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 수의 등장 횟수가 커지는 순으로, 그게 여러가지면 수가 커지는 순으로 정렬한다.

예를 들어 [3, 1, 1] 이라면 3이 1번, 1가 2번이므로 [3, 1, 1, 2]가 된다. 이걸 다시 정렬하면 3이 1번, 1이 2번, 2가 1번이므로 [2, 1, 3, 1, 1, 2]가 된다.

입력으로 r, c, k가 주어질 때 A배열의 A[r][c]가 k가 되는 최소 시간을 구한다. 단, 100초가 지나면 -1을 출력한다.

 

 

문제 해결 아이디어

단순하게 구현했다.

 

먼저 현재 행 또는 열의 배열을 nowArr로 할당해 놓고, 그 배열을 다 돌면서 해당하는 수가 몇 개 나왔는지 cnt 배열에 저장했다. cnt[2] = 3이면 2가 3번 나온 거다. 이 과정을 거치면서 수가 몇 개 등장했는지 maxCnt에 저장했다.

 

다음 과정으로는 그 cnt 배열을 돌면서 1부터 100까지 나온 수에 해당하는 숫자와, 수를 ArrayList에 저장했다. 이게 정렬의 과정이다. 이중 for문이라 상당히 거슬리지만 어쨌든 100번이 최대라 그냥 했다. ㅠㅠ

그 와중에 조금이라도 반복 줄여 보려고 아까 저장한 maxCnt + 2가 되면 (정렬이 다 되면) for문을 탈출한다.

 

마지막으로 정렬되어 ArrayList에 저장되어 있는 걸 하나하나 꺼내서 원래의 배열 A에 저장한다. 이 과정에서 만약 배열이 줄어들었다면, 원래 있던 숫자를 0으로 바꿔주어야 한다. 여기서!! 조금이라도 줄여보려고 0으로 바꾸는 걸 제한 뒀다가 결과가 제대로 안 나왔다... 디버깅 엄청 오래 해서 잡아냈다... ㅠ 이 방법밖에 없는 건 아닐텐데..

R연산과 C연산에서 약간의 차이가 있지만 알고리즘 자체는 똑같다.

 

매 연산이 실행될 때마다 행 또는 열은 늘어나므로 maxR, maxC 값을 변경해 주었다. 그 값을 기준으로 R 연산을 실행할지, C연산을 실행할지 결정한다. 만약 R 연산을 하다가 배열이 늘어나면 열이 늘어나는 것이므로 maxC를 바꿔 준다.

 

일단 풀고 싶어서 처음 생각했던 대로 풀었는데 다 풀고 나니까 너무 마음에 안 든다 일단 메모리를 너무 많이 낭비한다는 점과 for문을 너무 많이 도는 것 같다는 점............. 다른 코드도 찾아봐야겠다. 어쨌든 오랜만에 푼 것에 의의를 두겠다... ^^

 

 

여담이지만 또 하나의 고민...... 알고리즘 푸는 거 자바스크립트로 풀어야 할까? 자바가 익숙해졌는데.. ㅎ ㅎ.

 

완성된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr;
	static int r, c, maxR, maxC;

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

		r = Integer.parseInt(st.nextToken()) - 1;
		c = Integer.parseInt(st.nextToken()) - 1;
		int k = Integer.parseInt(st.nextToken());

		arr = new int[100][100];

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

		maxR = 3;
		maxC = 3;
		int result = -1;

		for (int i = 0; i <= 100; i++) {

			if (arr[r][c] == k) {
				result = i;
				break;
			}

			if (maxR >= maxC) {
				R();

			} else {
				C();
			}

		}

		System.out.println(result);
	}

	public static void R() {
		for (int i = 0; i < maxR; i++) {
			int[] nowArr = arr[i];
			int[] cnt = new int[101];
			int maxCnt = 0;
			for (int j = 0; j < nowArr.length; j++) {
				cnt[nowArr[j]]++;
				if (cnt[nowArr[j]] == 1 && nowArr[j] != 0)
					maxCnt++;
			}

			ArrayList<Integer> newArr = new ArrayList<>();
			maxC = Math.max(maxC, maxCnt * 2);

			for (int k = 1; k <= 100; k++) {
				if (newArr.size() == maxCnt * 2)
					break;
				for (int p = 1; p <= 100; p++) {
					if (cnt[p] == k) {
						newArr.add(p);
						newArr.add(k);
					}
				}
			}

			for (int j = 0; j < newArr.size(); j++) {
				arr[i][j] = newArr.get(j);
			}

			for (int j = newArr.size(); j < arr.length; j++) {
				arr[i][j] = 0;
			}
		}
	}

	public static void C() {
		for (int j = 0; j < maxC; j++) {
			int[] nowArr = new int[101];
			int[] cnt = new int[101];
			for (int i = 0; i < arr.length; i++) {
				nowArr[i] = arr[i][j];
			}

			int maxCnt = 0;
			for (int i = 0; i < nowArr.length; i++) {
				cnt[nowArr[i]]++;
				if (cnt[nowArr[i]] == 1 && nowArr[i] != 0)
					maxCnt++;

			}
			ArrayList<Integer> newArr = new ArrayList<>();
			maxR = Math.max(maxR, maxCnt * 2);

			for (int k = 1; k <= 100; k++) {
				if (newArr.size() == maxCnt * 2) {
					break;
				}
				for (int p = 1; p <= 100; p++) {
					if (cnt[p] == k) {
						newArr.add(p);
						newArr.add(k);
					}
				}
			}
			for (int i = 0; i < newArr.size(); i++) {
				arr[i][j] = newArr.get(i);
			}

			for (int i = newArr.size(); i < arr.length; i++) {
				arr[i][j] = 0;
			}
		}

	}
}