BOJ - 이차원 배열과 연산 17140번 (JAVA)

❓ 문제 - 백준 이차원 배열과 연산 17140번 - JAVA 풀이법

 

출처 

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

17140번: 이차원 배열과 연산

 

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 배열 A에 들어갈 수 있는 수는 100보다 작으므로 2차원 배열을 101*101 사이즈로 미리 만들어 놓고 연산된 정보 값을 관리한다.
• A[r][c]에 특정 k 값이 존재할 때까지 연산을 반복하다가 만약 연산 횟수가 101번이 되면 연산을 종료하고 -1을 출력한다.
• 현재 최대 행의 크기나 최대 열의 크기를 비교해서 R연산을 할지 C 연산을 할지 갱신한다.
•  R연산을 수행하면 최대 열의 크기가 변경되고 C연산을 수행하면 최대 행의 크기가 변경된다.
• R연산과 C연산을 수행할 때 hashmap을 활용하여 특정 숫자가 몇 번 나왔는지를 저장하고 list에 값을 넣어줘서 해당 숫자의 갯수의 오름차순, 그리고 갯수가 같다면 숫자의 오름차순 으로 정렬해준다.
• 정렬된 값의 숫자의 갯수, 숫자에  춰  map_copy에 넣어주고 map_copy의 값을 기존 map에 복사한다. 그리고 배열에 들어갈 수 있는 수는 100을 넘지 못하므로 이것도 맞춰서 구현처리 해준다.

 

💻 소스코드

// BOJ - 이차원 배열과 연산(17140번)
// 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main_17140 {
	public static int[][] map;
	public static int row_len, col_len;
	public static class Node implements Comparable<Node>{
		int num;
		int cnt;
		public Node(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		@Override
		public int compareTo(Node o) {
			if(this.cnt == o.cnt) {
				return this.num - o.num;
			}
			return this.cnt - o.cnt;
		}
		
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		map = new int[101][101];
		for(int i=0;i<3;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<3;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		row_len = 3;
		col_len = 3;
		
		int ans = -1;
		int cnt = 0;
		while(cnt <= 100) {
			if(map[r-1][c-1] == k) {
				ans = cnt;
				break;
			}
			
			if(row_len >= col_len) {
				row_cal();
			} else {
				col_cal();
			}


			cnt++;

		}
		
		System.out.println(ans);
	}
	
	public static void row_cal() {
		int[][] map_copy = new int[101][101];
		int col = 0;
		for(int i=0;i<row_len;i++) {
			HashMap<Integer, Integer> hash = new HashMap<>();
			for(int j=0;j<col_len;j++) {
				if(map[i][j] == 0) continue;
				if(hash.containsKey(map[i][j])) {
					hash.put(map[i][j], hash.get(map[i][j])+1);
				} else {
					hash.put(map[i][j], 1);
				}
			}
			ArrayList<Node> list = new ArrayList<>();
			for(Map.Entry<Integer, Integer> entry:hash.entrySet()) {
				list.add(new Node(entry.getKey(), entry.getValue()));
			}
			col = Math.max(col, list.size()*2);
			Collections.sort(list);
			for(int p=0;p<list.size();p++) {
				if(p >= 50) break;
				Node node = list.get(p);
				map_copy[i][2*p] = node.num;
				map_copy[i][2*p+1]= node.cnt;
			}
		}
		col_len = Math.min(99, col);
		map = map_copy;
	}
	
	public static void col_cal() {
		int[][] map_copy = new int[101][101];
		int row = 0;
		for(int j=0;j<col_len;j++) {
			HashMap<Integer, Integer> hash = new HashMap<>();
			for(int i=0;i<row_len;i++) {
				if(map[i][j] == 0) continue;
				if(hash.containsKey(map[i][j])) {
					hash.put(map[i][j], hash.get(map[i][j])+1);
				} else {
					hash.put(map[i][j], 1);
				}
			}
			ArrayList<Node> list = new ArrayList<>();
			for(Map.Entry<Integer, Integer> entry:hash.entrySet()) {
				list.add(new Node(entry.getKey(), entry.getValue()));
			}
			row = Math.max(row, list.size()*2);
			Collections.sort(list);
			for(int p=0;p<list.size();p++) {
				if(p >= 50) break;
				Node node = list.get(p);
				map_copy[2*p][j] = node.num;
				map_copy[2*p+1][j]= node.cnt;
			}
		}
		row_len = Math.min(99, row);
		map = map_copy;
	}

}