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

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

풀이

문제에서 요구한대로 코드를 작성하여 해결했습니다.

자세한 내용은 코드의 주석을 참고해주세요.

코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { public static class Info implements Comparable { int num, cnt; public Info(int num, int cnt) { this.num = num; this.cnt = cnt; } @Override public int compareTo(Info o) { // 문제의 조건에서 나온 횟수가 많은 순으로 정렬을 시킨다 int diff = Integer.compare(this.cnt, o.cnt); // 만약 나온 횟수가 같다면 숫자가 큰 순으로 정렬을 시킨다. return (diff == 0) ? Integer.compare(this.num, o.num) : diff; } } public static int r, c, k, maxR, maxC, answer; public static int[][] arr; 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; 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()); } } // 처음 시작때 최대 행과 열은 3 maxR = 3; maxC = 3; answer = getTime(); System.out.println(answer); } public static int getTime() { int time = 0; // 배열의 (r, c) 위치의 값이 k가 아니고 time이 100을 넘지 않을때까지 반복 while (arr[r][c] != k && time <= 100) { // 문제의 조건에 따라 현재 배열의 R이 길면 R 함수로 // 현재 배열의 C가 길면 C 함수로 보낸다. if (maxR >= maxC) { R(); } else { C(); } // 처리를 했으므로 시간 +1 time++; } // 만약 time이 100이넘는다면 -1을 아니라면 시간을 그대로 리턴 return (time > 100) ? -1 : time; } public static void R() { // 가장 긴 길이를 저장 int maxCol = maxC; for (int i = 0; i < maxR; ++i) { // 맵을 사용하여 숫자의 나온 횟수를 구한다. Map map = new HashMap<>(); for (int j = 0; j < maxC; ++j) { // 0이라면 숫자의 개수를 셀 필요가 없으므로 다음 숫자가 0이 아닌 수일 수 있기에 계속 탐색 if (arr[i][j] == 0) { continue; } // 만약 맵에 포함된 숫자라면 기존 cnt에 +1을 아니라면 1을 맵에 넣는다 if (map.containsKey(arr[i][j])) { map.put(arr[i][j], map.get(arr[i][j]) + 1); } else { map.put(arr[i][j], 1); } } // 정렬을 우선순위 큐를 사용해 수행 PriorityQueue pq = new PriorityQueue<>(); // map에 든 값들을 pq에 삽입 for (int num : map.keySet()) { pq.add(new Info(num, map.get(num))); } int col = 0; // 문제의 조건에 의해 배열의 길이는 100이 넘어가면 안되므로 100까지만 반복 while (!pq.isEmpty() && col < 100) { Info info = pq.poll(); arr[i][col++] = info.num; arr[i][col++] = info.cnt; } // 가장 긴 길이를 저장한다. if (maxCol < col) { maxCol = col; } else { // 가장 긴 길이가 아니라면 오히려 기존의 길이보다 짧아졌을 수 도 있기 때문에 // 짧아진 길이만큼 그 공간을 0으로 만들어 준다. for (int j = col; j < maxC; ++j) { arr[i][j] = 0; } } } // 다음 R함수나 C함수를 위해 현재까지 구한 가장 긴 길이를 저장한다. maxC = maxCol; } public static void C() { // 가장 긴 길이를 저장 int maxRow = maxR; for (int i = 0; i < maxC; ++i) { // 맵을 사용하여 숫자의 나온 횟수를 구한다. Map map = new HashMap<>(); for (int j = 0; j < maxR; ++j) { // 0이라면 숫자의 개수를 셀 필요가 없으므로 다음 숫자가 0이 아닌 수일 수 있기에 계속 탐색 if (arr[j][i] == 0) { continue; } // 만약 맵에 포함된 숫자라면 기존 cnt에 +1을 아니라면 1을 맵에 넣는다 if (map.containsKey(arr[j][i])) { map.put(arr[j][i], map.get(arr[j][i]) + 1); } else { map.put(arr[j][i], 1); } } // 정렬을 우선순위 큐를 사용해 수행 PriorityQueue pq = new PriorityQueue<>(); // map에 든 값들을 pq에 삽입 for (int num : map.keySet()) { pq.add(new Info(num, map.get(num))); } int row = 0; // 문제의 조건에 의해 배열의 길이는 100이 넘어가면 안되므로 100까지만 반복 while (!pq.isEmpty() && row < 100) { Info info = pq.poll(); arr[row++][i] = info.num; arr[row++][i] = info.cnt; } if (maxRow < row) { maxRow = row; } else { // 가장 긴 길이가 아니라면 오히려 기존의 길이보다 짧아졌을 수 도 있기 때문에 // 짧아진 길이만큼 그 공간을 0으로 만들어 준다. for (int j = row; j < maxR; ++j) { arr[j][i] = 0; } } } // 다음 R함수나 C함수를 위해 현재까지 구한 가장 긴 길이를 저장한다. maxR = maxRow; } }

from http://comgong-man.tistory.com/235 by ccl(A) rewrite - 2021-09-09 16:27:23