Baekjoon[17140] - 이차원 배열과 연산

링크

17140번: 이차원 배열과 연산

문제설명

• BFS,DFS인줄알고 풀었는데 시뮬이었다
• 하라는대로 하면됨

문제풀이

• 숫자개수 세아리는건 frequency Array생성함(Hashmap만들어도 됐음)
• R연산 C연산 각각 처리해줘야 함.

문제코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.StringTokenizer;



public class Main {

    public static int r;
    public static int c;
    public static int k;

    public static int[][] A = new int[100][100];

    public static int[] freq;
    public static int rlen = 3;
    public static int clen = 3;

    public static int Ans = 0;

    public static Comparator<int[]> comp = new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            // TODO Auto-generated method stub
            if(o1[1]==o2[1]) {
                return o1[0]-o2[0];
            }
            else {
                return o1[1]-o2[1];
            }
        }
    }; 

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        while(Ans<=100) {
//            확인하기
            if(A[r-1][c-1]==k) {
                break;
            }

//            R연산 C연산
            if(rlen>=clen) {
//                R연산
//                빈도수 연산하기
                for (int r_ = 0; r_ < 100; r_++) {

                    freq = new int[101];
                    LinkedList<int[]> ll = new LinkedList<int[]>();

                    for (int i = 0; i < 100; i++) {
                        freq[A[r_][i]]++;
                    }

                    for (int i = 1; i <= 100; i++) {
                        if(freq[i]>0) {
                            ll.add(new int[] {i,freq[i]});
                        }
                    }    

//                    정렬하기
//                    ll.sort(new Comparator<int[]>() {
//                        @Override
//                        public int compare(int[] o1, int[] o2) {
//                            // TODO Auto-generated method stub
//                            if(o1[0]==o2[0]) {
//                                return o2[1]-o1[1];
//                            }
//                            else {
//                                return o2[0]-o1[0];
//                            }
//                        }
//                    });

                    ll.sort(comp);

//                    바꾸기
                    clen = Math.max(clen, ll.size()*2);
                    for (int i = 0; i < 100; i++) {
                        A[r_][i] = 0;
                    }
                    for (int i = 0, lsize = ll.size(); i < Math.min(50,lsize); i++) {
                        int[] temp = ll.poll();
                        A[r_][i*2] = temp[0];
                        A[r_][i*2+1] = temp[1];
                    }
                }
            }
            else {
//                C연산
//                빈도수 연산하기
                for (int c_ = 0; c_ < 100; c_++) {

                    freq = new int[101];
                    LinkedList<int[]> ll = new LinkedList<int[]>();

                    for (int i = 0; i < 100; i++) {
                        freq[A[i][c_]]++;
                    }

                    for (int i = 1; i <= 100; i++) {
                        if(freq[i]>0) {
                            ll.add(new int[] {i,freq[i]});
                        }
                    }    

//                    정렬하기
//                    ll.sort(new Comparator<int[]>() {
//                        @Override
//                        public int compare(int[] o1, int[] o2) {
//                            // TODO Auto-generated method stub
//                            if(o1[0]==o2[0]) {
//                                return o2[1]-o1[1];
//                            }
//                            else {
//                                return o2[0]-o1[0];
//                            }
//                        }
//                    });

                    ll.sort(comp);

//                    바꾸기
                    rlen = Math.max(rlen, ll.size()*2);
                    for (int i = 0; i < 100; i++) {
                        A[i][c_] = 0;
                    }
                    for (int i = 0, lsize = ll.size(); i < Math.min(50,lsize); i++) {
                        int[] temp = ll.poll();
                        A[i*2][c_] = temp[0];
                        A[i*2+1][c_] = temp[1];
                    }
                }
            }
            Ans++;
        }

        if(Ans>100) {
            System.out.println(-1);
        }
        else {
            System.out.println(Ans);
        }

//        초기화
        Ans = 0;
    }
}

아쉬운 점

• 문제 제대로 안읽음
  • R, C 이렇게 각각 행,열 연산이 따로 있는데 R 연산만 고려했었음.
• LinkedList for문에서 돌릴 때, lsize가 동적으로 변하는것 고려못했음
  • lsize int선언 해주던가 돌때마다 관리해줘야 함.
• 정렬 시 오름차순, 내림차순 헷갈림...
  • 오름차순 : 1,2,3,4, ...
    • o1-o2
  • 내림차순 : 4,3,2,1, ...
    • o2-o1
• 정렬 시 우선순위 잘못뒀음
  • o1를 우선고려했어야 하는데 그렇게 안했음.
• 인덱싱 실수
  • 흔한 행,열 헷갈림
• 실수가 많아서 시간이 오래 걸림(1:30)

잘한 점

• O(N) = 최대횟수(100) * {행|열(100)*(빈도수(100)+정렬(100log_100)} = 10^7 쯤?
• comparator 변수를 예전엔 클래스 써서 했던거 같은데, 아무튼 정렬함수를 static에 생성해놓고 호출함.