[BOJ/Java] 17140 : 이차원 배열과 연산

문제

 

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

 

풀이

 

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] map;
	static int[][] temp;
	static int r, c, k, rLength, cLength;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.readLine());
		r = Integer.parseInt(st.nextToken()) - 1;
		c = Integer.parseInt(st.nextToken()) - 1;
		k = Integer.parseInt(st.nextToken());
		map = new int[3][3];
		
		for (int i = 0; i < 3; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < 3; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int time = 0;
		while (true) {

			if (time == 0) {
				rLength = 3;
				cLength = 3;
			}
			if (r >= 0 && c >= 0 && r < rLength && c < cLength) {
				if (map[r][c] == k) {
					System.out.println(time);
					return;
				}
			}

			if (rLength >= cLength) {
				int maxLength = 0;
				temp = new int[101][101];
				for (int i = 0; i < rLength; i++) {

					int[] count = new int[101];
					int number = 0;

					// 숫자 빈도수 채우기
					for (int j = 0; j < cLength; j++) {
						if (map[i][j] != 0) {
							count[map[i][j]]++;
						}
					}

					ArrayList<Count> list = new ArrayList<>(); // list에 Count타입의 객체를 넣어준다(숫자,빈도수)
					for (int j = 1; j <= 100; j++) {
						if (count[j] != 0) {
							list.add(new Count(j, count[j]));
							number = list.size();
						}
					}

					Collections.sort(list); // 우선순위에 따라 sort
					

					int cur = 0;
					for (Count l : list) {
						temp[i][cur++] = l.val;
						temp[i][cur++] = l.cnt;
					}
					maxLength = Math.max(number, maxLength);

				}
				cLength = maxLength * 2;
				map = new int[rLength][cLength]; // 열의 최대길이만큼 map의 크기를 다시 만들어줌

				// map에 임시저장 해두었던 temp배열 값을 옮겨준다
				for (int i = 0; i < rLength; i++) {
					for (int j = 0; j < cLength; j++) {
						map[i][j] = temp[i][j];
					}
				}
				
			} else {
				int maxLength = 0;
				temp = new int[101][101];
				for (int j = 0; j < cLength; j++) {

					int[] count = new int[101];
					int number = 0;

					// 숫자 빈도수 채우기
					for (int i = 0; i < rLength; i++) {
						if (map[i][j] != 0) {
							count[map[i][j]]++;
						}
					}

					ArrayList<Count> list = new ArrayList<>(); // list에 Count타입의 객체를 넣어준다(숫자,빈도수)
					for (int i = 1; i <= 100; i++) {
						if (count[i] != 0) {
							list.add(new Count(i, count[i]));
							number = list.size();
						}
					}

					Collections.sort(list); // 우선순위에 따라 sort

					int cur = 0;

					for (int i = 0; i < list.size(); i++) {
						temp[cur++][j] = list.get(i).val;
						temp[cur++][j] = list.get(i).cnt;
					}
					maxLength = Math.max(number, maxLength);

				}
				rLength = maxLength * 2;
				map = new int[rLength][cLength]; // 열의 최대길이만큼 map의 크기를 다시 만들어줌

				// map에 임시저장 해두었던 temp배열 값을 옮겨준다
				for (int i = 0; i < rLength; i++) {
					for (int j = 0; j < cLength; j++) {
						map[i][j] = temp[i][j];
					}
				}
			}

			time++;
			if (time > 100) {
				System.out.println(-1);
				return;
			}
		}
	}

	static class Count implements Comparable<Count> {
		int val;
		int cnt;

		Count(int val, int cnt) {
			this.val = val;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Count o) {
			int diff = this.cnt - o.cnt;
			return diff == 0 ? this.val - o.val : diff;
		}
	}
}

 

 

 

 

느낀점

 

• Comparable 인터페이스 상속받고 compareTo 함수 이용해서 우선순위 설정하는 건 익숙하지 않아서 알고리즘 풀 때 잘 사용하지 않았는데, 확실히 코드 길이가 줄어든다!