백준 17140번: 이차원 배열과 연산

문제 설명

• https://www.acmicpc.net/problem/17140
• 2차원 배열이 지닌 행,열의 개수에 따라 어떤 함수를 실행합니다.
  • 행의 개수>=열의 개수면 행 방향으로 함수를 실행합니다.
  • 행의 개수<열의 개수면 열 방향으로 함수를 실행합니다.
• 어떤 함수는 다음과 같습니다.
  • 2차원 배열의 각 행 또는 각 열에 대해 아래의 과정을 진행합니다.
    • 하나의 행 또는 열은 1차원 배열입니다.
    • 1차원 배열 속 원소가 몇 개 들어있는지를 구하고, 기준에 따라 정렬한 뒤 결과를 반환합니다.
    • 정렬기준은 들어있는 개수가 많은 숫자부터, 동일하면 큰 숫자부터 반환합니다.
    • [3,1,1,2] 배열로 예시를 들어보겠습니다.
      • 위 배열은 {3:1개,1:2개,2:1개}가 있습니다.
      • 순서에 맞게 정렬하면 {1:2,3:1,2:1}가 됩니다.
        • 1이 2개있기 때문에 가장 먼저 나옵니다.
        • 3과 1은 둘 다 1개씩 있지만 3>2이기 때문에 3이 앞에 존재합니다.
      • 이를 배열로 반환하면 [1,2,3,1,2,1]이 됩니다.
  • 결과로 얻은 배열 중 가장 길이가 긴 배열을 기준으로 정합니다.
    • 기준보다 길이가 짧은 배열은 오른쪽을 0으로 채워 길이를 맞춥니다.
    • 예시)
      • 각 행별로 작업을 진행한 결과가 [1,1,2,1],[1,1],[1,1,2,1,3,1]이라면
        • [1,1,2,1,3,1]이 기준이 됩니다,
        • [1,1,2,1]은 [1,1,2,1,0,0]이 됩니다.
        • [1,1]은 [1,1,0,0,0,0]이 됩니다.
        • 최종적으로 [[1,1,2,1,0,0],[1,1,0,0,0,0],[1,1,2,1,3,1]]이 됩니다.

접근법

• 배열에 어떤 숫자가 몇개 들어있는가?를 두 가지 방법으로 체크할 수 있습니다.
  • 배열에 들어가는 자연수는 100보다 작기 때문에 100크기의 배열을 만들고 사용횟수를 체크할 수 있습니다.
  • (key,value)쌍의 HashMap을 만들어 key값으로 배열 속 자연수, value값으로 자연수가 등장한 횟수를 표현할 수 있습니다.

pseudocode

main(){
	while(true){
        if(원하는 값을 찾으면 || 100번이 넘어가면){
        	break
        }
    
    	if(행의 개수>=열의 개수){
        	arr = R(arr) // 행을 기준으로 함수 실행
        }else{
        	arr = C(arr) // 열을 기준으로 함수 실행
        }
    }
}

R(2차원 배열){
	func(2차원 배열의 각 행)
    가장 긴 결과값을 기준으로 미달하는 배열은 오른쪽을 0으로 채움
    새로운 배열에 행방향으로 값을 채움
}

C(2차원 배열){
	func(2차원 배열의 각 열)
    가장 긴 결과값을 기준으로 미달하는 배열은 오른쪽을 0으로 채움
    새로운 배열에 열방향으로 값을 채움
}

func(1차원 배열){
	1차원 배열에 어떤 값이 몇번 들어갔는지를 map으로 표현
}

정답

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int c = sc.nextInt();
		int k = sc.nextInt();
		int[][] arr = new int[3][3];
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		int time = 0;
		while (true) {

			if (0 <= r - 1 && r - 1 < arr.length && 0 <= c - 1 && c - 1 < arr[0].length && arr[r - 1][c - 1] == k)
				break;
			time++;
			if (time > 100) break; // "100초가 지나면" 은 100초까지는 OK, 101초부터 안된다는 의미입니다.
			int rNum = arr.length;
			int cNum = arr[0].length;
			if (rNum >= cNum) {
				arr = R(arr);
			} else {
				arr = C(arr);
			}
		}
		System.out.println((time > 100) ? -1 : time);

	}

	public static int[][] R(int[][] board) {
		int size = 0;
		List<List<Obj>> a = new ArrayList<List<Obj>>();

		for (int i = 0; i < board.length; i++) {
			a.add(func(board[i]));
			size = Math.max(size, a.get(i).size());
		}
		for (int i = 0; i < a.size(); i++) {
			while (a.get(i).size() < size) {
				a.get(i).add(new Obj(0, 0));
			}
		}

		int r = Math.min(100, a.size());
		int c = Math.min(100, size * 2);
		int[][] NewBoard = new int[r][c];
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j = j + 2) {
				// [key값, value값, ...] 형태로 넣습니다.
				NewBoard[i][j] = a.get(i).get(j / 2).num; 
				NewBoard[i][j + 1] = a.get(i).get(j / 2).cnt; 
			}
		}
		return NewBoard;
	}

	public static int[][] C(int[][] board) {
		int size = 0;
		List<List<Obj>> a = new ArrayList<List<Obj>>();
		
		for (int j = 0; j < board[0].length; j++) {
			int[] arr = new int[board.length];
			for (int i = 0; i < board.length; i++) {
				arr[i] = board[i][j]; // j열 데이터를 담습니다.
			}
			
			a.add(func(arr)); // j열 배열에 어떤 원소가 몇 개 있는지 계산한 뒤 a에 넣습니다.
			size = Math.max(size, a.get(j).size()); 
		}
		
		// 가장 긴 배열을 기준으로 미달하는 배열들은 0을 채웁니다.
		for (int i = 0; i < a.size(); i++) {
			while (a.get(i).size() < size) {
				a.get(i).add(new Obj(0, 0));
			}
		}

		int r = Math.min(100, a.size());
		int c = Math.min(100, size * 2);

		int[][] NewBoard = new int[2 * size][a.size()];
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j = j + 2) {
				NewBoard[j][i] = a.get(i).get(j / 2).num;
				NewBoard[j + 1][i] = a.get(i).get(j / 2).cnt;
			}
		}
		return NewBoard;
	}

	// 1차원 배열에 어떤 원소가 몇 개 있는지를 확인하는 함수입니다.
	// 배열 속 숫자는 map의 key이고 value는 해당 숫자가 등장한 개수입니다.
	public static List<Obj> func(int[] arr) {
		List<Obj> lst = new ArrayList<Obj>();
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < arr.length; i++) {
			int key = arr[i];
			if (map.containsKey(key)) {
				map.put(key, map.get(key) + 1);
			} else {
				if (key == 0) continue; // 0은 세지 않습니다.
				map.put(key, 1);
			}
		}
		for (Integer k : map.keySet()) {
			lst.add(new Obj(k, map.get(k)));
		}
		Collections.sort(lst);
		return lst;

	}

	static class Obj implements Comparable<Obj> {
		int num;
		int cnt;

		public Obj(int num, int cnt) {
			super();
			this.num = num;
			this.cnt = cnt;
		}

		@Override
		public String toString() {
			return "Obj [num=" + num + ", cnt=" + cnt + "]";
		}

		@Override
		public int compareTo(Obj o) {
			return (this.cnt != o.cnt) ? this.cnt - o.cnt : this.num - o.num; // 개수가 큰 걸 앞으로, 개수가 같으면 숫자가 큰 걸 앞으로 정렬합니다.
		}

	}
}