[백준] 17140. 이차원 배열과 연산 (Java)

 

🔒 문제

17140번: 이차원 배열과 연산

 

 

🔑 알고리즘

구현, 정렬, 해시맵(HashMap)

 

 

💡  풀이

 

각 행과 열의 원소들을 배열에 저장할 수도 있고, 리스트에 저장할 수도 있을 것이다.

배열에 저장하면 임의 접근은 쉬우나 문제 특성 상 각 행과 열의 크기가 달라지기 때문에 크기를 지정하는데 어려움이 있고,

리스트에 저장하면 행과 열의 크기가 변화해도 지장이 없으나 임의 접근이 불가능하므로 행, 열 두 가지 정렬을 모두 수행할 수 없다.

 

(1 ≤ r, c, k ≤ 100)
행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

문제에 위와 같은 조건이 있으므로 100x100 크기의 배열을 사용하되,

각 행과 열의 유효한 원소(0이 아닌 원소)의 마지막 인덱스를 저장할 배열을 사용하였다.

 

 

다음과 같은 원소가 있다면 (예제 1~5)

1 2 1
2 1 3
3 3 3

각 행과 열의 크기는 3이고, 유효한 원소의 마지막 인덱스 또한 모두 3이 된다.

 

따라서 다음과 같이 표현할 수 있다.

배열의 크기는 100x100이나 편의상 7x7 배열로 표현, 빈칸에는 0이 삽입되어있음

 

행의 개수 ≥ 열의 개수이므로 R 연산을 수행한다.

 

이때 각각의 수의 등장 횟수를 체크해야하는데, 배열을 사용할 수도 있고, 맵을 사용할 수도 있다.

배열 A에 들어있는 수는 100보다 작거나 같은 자연수라는 조건이 있으므로 배열을 사용할 수도 있지만

그러면 원소가 1개인 경우에도 크기 100의 배열을 모두 탐색해야하므로 비효율적이다.

 

따라서 등장하는 값을 Key, 등장 횟수를 Value 로 하는 맵을 사용하였고,

정렬을 지원하는 TreeMap을 사용할 수도 있지만 정렬 조건에 등장 횟수인 Value가 포함되어있고, TreeMap은 Value로 정렬할 수 없기 때문에 HashMap을 사용하였다.

 

현재 배열 A는 3행까지 있으므로 rowCount인 3까지 각 행을 돌면서 정렬하고 배열 A를 갱신한다.

1행을 예로 들면 1행의 마지막 유효 원소 인덱스인 rowIndex[1] 까지 탐색하면서 원소를 Map에 삽입하는데,

이때 정렬하여 새로 만들어질 배열이 기존 크기보다 작아질 수 있다.

 

예를 들어, 1 1 1을 정렬하면, 1이 3개이므로 1 3이 되는데 맨 뒤의 1이 남아있으므로 1 3 1 이 된다.

따라서 원소를 탐색할 때, 배열 A의 값을 0으로 바꿔주어 이를 해결한다.

 

for (int j = 0; j < rowIndex[i]; j++) {
	if (A[i][j] != 0) {
		hashMap.put(A[i][j], hashMap.getOrDefault(A[i][j], 0) + 1);
		A[i][j] = 0;
	}
}

 

 

따라서 1행을 전부 탐색하면

map에 {1, 2} {2, 1} 의 원소가 삽입되어있고, 이를 우선순위 큐에 담아서 정렬한다.

for (Integer key : hashMap.keySet()) {
	pq.add(new Number(key, hashMap.get(key)));
}

 

 

이제 우선순위 큐의 원소를 배열 A에 삽입하고 이를 A에  삽입하고,

행의 길이가 3에서 4로 늘었기 때문에 rowIndex[1] 과 colCount를 3에서 4로 갱신한다.

rowIndex[i] = hashMap.size() * 2;

for (int j = 0; j < rowIndex[i] && j < 100; j += 2) {
	Number cur = pq.poll();
	A[i][j] = cur.num;
	A[i][j + 1] = cur.count;
}

if (rowIndex[i] > colCount) {
	colCount = rowIndex[i];
}

 

같은 방식으로 rowCount인 3행까지 정렬을 마치고나면 다음 상태가 된다.

rowCount는 변하지 않겠지만 colIndex가 수정되어야함을 알 수 있다.

colIndex는 마지막 행부터 첫 행까지 거꾸로 내려오면서 해당 행의 rowIndex 값까지의 colIndex를 수정하면 된다.

 

위의 상황에서는

3행의 rowIndex가 3이므로 colIndex[1], colIndex[2], colIndex[3] 을 3으로 수정하고

2행의 rowIndex가 6이므로 colIndex[4], colIndex[5], colIndex[6] 을 2로 수정하고

1행의 rowIndex가 4지만 colIndex가 모두 1보다 크기 때문에 수정되지 않는다.

rowIndex = new int[100];
for (int i = colCount - 1; i >= 0; i--) {
	for (int j = colIndex[i] - 1; j >= 0; j--) {
		if (rowIndex[j] < i + 1)
			rowIndex[j] = i + 1;
	}
}

 

C 연산도 행과 열만 바뀌고 R 연산과 동일하다.

 

 

 

* 설명 및 그림은 인덱스가 1부터 시작하는 것으로 했지만 코드는 0부터 시작하였다.

* 맵과 우선순위 큐는 각 행, 열의 연산을 할때마다 초기화해주어야한다.

 

 

✏️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static HashMap<Integer, Integer> hashMap;
	static PriorityQueue<Number> pq;
	static int[][] A;
	static int[] rowIndex;
	static int[] colIndex;
	static int rowCount;
	static int colCount;

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

		A = new int[100][100];
		rowIndex = new int[100];
		colIndex = new int[100];
		rowCount = 3;
		colCount = 3;
		pq = new PriorityQueue<>();
		hashMap = new HashMap<>();

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

		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());
				colIndex[j]++;
				rowIndex[i]++;
			}
		}

		int t = 0;
		while (true) {

			// A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다.
			if (A[r - 1][c - 1] == k) {
				System.out.println(t);
				return;
			}

			// 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.
			if (t > 100) {
				System.out.println(-1);
				return;
			}

			// R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
			// C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
			if (rowCount >= colCount)
				R();
			else
				C();

			t++;
		}
	}

	private static void R() {
		int tmp = rowCount;
		colCount = Integer.MIN_VALUE;
		for (int i = 0; i < tmp; i++) {
			pq.clear();
			hashMap.clear();

			for (int j = 0; j < rowIndex[i]; j++) {
				if (A[i][j] != 0) {
					hashMap.put(A[i][j], hashMap.getOrDefault(A[i][j], 0) + 1);
					A[i][j] = 0;
				}
			}

			rowIndex[i] = hashMap.size() * 2;
			for (Integer key : hashMap.keySet()) {
				pq.add(new Number(key, hashMap.get(key)));
			}

			for (int j = 0; j < rowIndex[i] && j < 100; j += 2) {
				Number cur = pq.poll();
				A[i][j] = cur.num;
				A[i][j + 1] = cur.count;
			}

			if (rowIndex[i] > colCount) {
				colCount = rowIndex[i];
			}
		}

		colIndex = new int[100];
		for (int i = rowCount - 1; i >= 0; i--) {
			for (int j = rowIndex[i] - 1; j >= 0; j--) {
				if (colIndex[j] < i + 1)
					colIndex[j] = i + 1;
			}
		}
	}

	private static void C() {
		int tmp = colCount;
		rowCount = Integer.MIN_VALUE;
		for (int i = 0; i < tmp; i++) {
			pq.clear();
			hashMap.clear();

			for (int j = 0; j < colIndex[i]; j++) {
				if (A[j][i] != 0) {
					hashMap.put(A[j][i], hashMap.getOrDefault(A[j][i], 0) + 1);
					A[j][i] = 0;
				}
			}

			colIndex[i] = hashMap.size() * 2;
			for (Integer key : hashMap.keySet()) {
				pq.add(new Number(key, hashMap.get(key)));
			}

			for (int j = 0; j < colIndex[i] && j < 100; j += 2) {
				Number cur = pq.poll();
				A[j][i] = cur.num;
				A[j + 1][i] = cur.count;
			}

			if (colIndex[i] > rowCount) {
				rowCount = colIndex[i];
			}
		}

		rowIndex = new int[100];
		for (int i = colCount - 1; i >= 0; i--) {
			for (int j = colIndex[i] - 1; j >= 0; j--) {
				if (rowIndex[j] < i + 1)
					rowIndex[j] = i + 1;
			}
		}
	}

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

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

		@Override
		public int compareTo(Number o) {
			return count == o.count ? num - o.num : count - o.count;
		}
	}
}