17140. 이차원 배열과 연산

문제 개요

이차원 배열의 행과 열에 존재하는 값의 개수를 비교하여 정렬하는 구현문제입니다.

문제 접근

단순히 정렬하는 것으로 풀 수 있는지 생각해보았을 때 반복횟수를 K, 열과 행의 길이 중 긴 것을 N이라고 할 때, KNlogN 은 최대 100*100log100이므로 완전탐색으로 가능할 것 같다는 생각이 들었습니다.

그래서 단순 구현으로 해결하였습니다.

백준에서는 Java11로 컴파일 되기 때문에 steram을 사용할 때 toList()메서드 대신 collect(Collectors.toList())로 바꿔야 하는 점 때문에 한번 틀렸습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.stream.Collectors;

public class Main {
    static int R;
    static int C;
    static int K;
    static final int MAXIMUM = 100;

    static int[][] mat;

    public static void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int[] values = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        mat = new int[MAXIMUM][MAXIMUM];
        R = values[0]-1;
        C = values[1]-1;
        K = values[2];
        for(int i=0;i<3;i++){
            int[] col = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for(int j=0;j<3;j++){
                mat[i][j] = col[j];
            }
        }
    }

    static boolean isEnd(){
        return mat[R][C] == K;
    }

    static int getMat(int i, int j, boolean isJCol){
        if(isJCol){
            return mat[i][j];
        }
        return mat[j][i];
    }

    static void setMat(int i, int j, int value, boolean isJCol){
        if(isJCol){
            mat[i][j] = value;
            return;
        }
        mat[j][i] = value;
    }

    public static List<Entry<Integer, Integer> > getSorted(int i, int size, boolean isJCol){
        Map<Integer, Integer> counts = new HashMap<>();
        //get count of values
        for(int j=0;j<size;j++){
            if(getMat(i, j, isJCol) == 0){
                continue;
            }
            if(counts.containsKey(getMat(i, j, isJCol))){
                counts.put(getMat(i, j, isJCol), counts.get(getMat(i, j, isJCol))+1);
                continue;
            }
            counts.put(getMat(i, j, isJCol), 1);
        }
        return counts.entrySet()
                        .stream()
                        .sorted(Comparator.comparing(Entry<Integer, Integer>::getValue)
                                        .thenComparing(Entry<Integer, Integer>::getKey))
                        .collect(Collectors.toList());
    }

    public static void setMatWithSorted(List<Entry<Integer, Integer> > sorted, int i, int size, boolean isJCol){
        for(int j=0;j<sorted.size();j++){
            setMat(i, j*2, sorted.get(j).getKey(), isJCol);
            setMat(i, j*2+1, sorted.get(j).getValue(), isJCol);
        }
        for(int j=sorted.size()*2;j<size;j++){
            setMat(i, j, 0, isJCol);
        }
    }

    public static void process(){
        int count = 0;
        int rows = 3;
        int cols = 3;

        while(!isEnd()){
            count++;
            if(count > 100){
                count = -1;
                break;
            }
            if(rows >= cols){
                //row operation
                for(int i=0;i<rows;i++){
                    var sorted = getSorted(i, cols, true);
                    setMatWithSorted(sorted, i, cols, true);
                    if(cols < sorted.size()*2){
                        cols = sorted.size()*2;
                    }
                }
                continue;
            }
            //col operation
            for(int i=0;i<cols;i++){
                var sorted = getSorted(i, rows, false);
                setMatWithSorted(sorted, i, rows, false);
                if(rows < sorted.size()*2){
                    rows = sorted.size()*2;
                }
            }
        }

        System.out.println(count);
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

문제

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