17140 이차원 배열과 연산 (Java)

이차원 배열과 연산

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

풀이

우선 행의 수와 열의 수를 비교해서 R 연산을 할지 C 연산을 할지 선택한다.
R 연산의 경우 모든 행에 대해서 문제에 나온 방식으로 정렬을 한다.
정렬하는 방식은 다음과 같다.

1. 하나의 행(list)을 순회하며 map에 수와 수가 나온 수를 저장한다.
2. map에 들어간 정보를 문제에 나온 방식으로 정렬하여 새로운 행(list)를 만든다.
   • 이 때 본인은 map의 정보들을 하나의 클래스(Node)에 담아 Comparable 인터페이스를 이용해 정렬하였다.
3. 모든 행에 대해 반복한 후 행의 길이를 맞추기 위해 모든 행의 길이를 0을 넣어가며 맞춘다.

C 연산의 경우 다음과 같이 해결한다.

1. 행과 열을 뒤집는다.
2. R 연산과 똑같은 과정을 반복한다.
3. 다시 행과 열을 뒤집는다.

이를 최대 while문을 통해 최대 100번까지 수행하고 도중에 r, c의 값이 k이면 break를 통해 탈출한다.
최종적으로 반복이 100번 초과이면 -1을 반환하고 그 이하이면 반복 수를 반환한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;

public class Main{

    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) {
            return o.cnt == cnt
                    ? num - o.num
                    : cnt - o.cnt;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "num=" + num +
                    ", cnt=" + 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());

        int ans = 0;

        List<List<Integer>> lists = new ArrayList<>();

        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            lists.add(new ArrayList<>());
            for (int j = 0; j < 3; j++) {
                lists.get(i).add(Integer.parseInt(st.nextToken()));
            }
        }


        while (ans <= 100) {

            if (lists.size() > r - 1 && lists.get(0).size() > c - 1) {
                if (lists.get(r - 1).get(c - 1) == k) {
                    break;
                }
            }
            int col = lists.size();
            int row = lists.get(0).size();
            ans++;

            // R 연산
            if (col >= row) {
                int maxSize = 0;
                for (int i = 0; i < col; i++) {
                    if (i >= 100) {
                        break;
                    }
                    lists.set(i, calR(lists.get(i)));
                    maxSize = Math.max(maxSize, lists.get(i).size());
                }
                for (int i = 0; i < col; i++) {
                    if (i >= 100) {
                        break;
                    }
                    while (maxSize > lists.get(i).size()) {
                        lists.get(i).add(0);
                    }
                }
                // C 연산
            }else{
                List<List<Integer>> temp = changeRowCol(lists);
                int maxSize = 0;
                for (int i = 0; i < row; i++) {
                    if (i >= 100) {
                        break;
                    }
                    temp.set(i, calR(temp.get(i)));
                    maxSize = Math.max(maxSize, temp.get(i).size());
                }
                for (int i = 0; i < row; i++) {
                    if (i >= 100) {
                        break;
                    }
                    while (temp.get(i).size() < maxSize) {
                        temp.get(i).add(0);
                    }
                }
                lists = changeRowCol(temp);
            }


        }

        System.out.println(ans > 100 ? -1 : ans);
    }

    static List<Integer> calR(List<Integer> list) {
        Map<Integer, Integer> map = new TreeMap<>();

        for (int i = 0; i < list.size(); i++) {
            Integer num = list.get(i);
            if (num == 0) {
                continue;
            }
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        Iterator<Integer> iter = map.keySet().iterator();

        // sorting
        List<Node> sort = new ArrayList<>();
        while (iter.hasNext()) {
            int num = (int)iter.next();
            int cnt = map.get(num);

            sort.add(new Node(num, cnt));
        }
        Collections.sort(sort);


        List<Integer> retList = new ArrayList<>();
        for (Node node : sort) {
            retList.add(node.num);
            retList.add(node.cnt);
        }

        return retList;
    }

    static List<List<Integer>> changeRowCol(List<List<Integer>> lists) {
        int col = lists.get(0).size();
        List<List<Integer>> ret = new ArrayList<>();
        // 초기화
        for (int i = 0; i < col; i++) {
            ret.add(new ArrayList<>());
        }


            // create new list
            for (List<Integer> list : lists) {
                for (int i = 0; i < col; i++) {
                    ret.get(i).add(list.get(i));
                }
            }
        return ret;
    }
}