백준[BOJ] 17140 -java

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

문제

아이디어

구현하는 부분을 총 3군데로 나눠야 겠다고 생각했다.

1. 입력부분 + count(초)세는 부분
   • 입력부분은 BufferReader 와 StringTokenizer로 해결하자
   • count 부분은 while문을 써서 map[r][c] =k 인 지 확인 하고, 100초 초과시 종료.
2. row 연산
3. col 연산

제약사항(내가 생각하는)

1. 100초 초과시 -1 반환 / 100초 이하 시 초 반환
2. 연산으로 하고 크기가 100 넘어가는건 자르기
3. 빈도수가 클수록 뒤로, 같은 빈도수 일때 숫자 크기로 정렬
4. 0은 무시
5. 열과 행의 크기는 유동적이고, 열과 행의 크기에 따라 연사는 하는 방식이 달라짐.
6. 연산은 모든 행/ 모든 열에서 이뤄짐.

그런데 row 연산과 col의 연산은 동일하니(가로로하나 세로로하나 의 차이 정도) 둘 중 하나만 다른 하나도 그대로 적용하면 되니 별 문제가 없다고 생각을 했다.

고민 리스트

1. 어떤 자료구조를 사용하지?

1-1. ArrayList

제약사항 5번 처럼 열과 행의 크기가 항상 바뀌니까 처음엔 ArrayList를 생각했는데..
Row 계산을 할때 얼마나 늘어날지 미리 알고 선언을 해주어야 한다는 단점이 있어서 PASS했다.

1-2. int [][]

1번에서 ArrayList가 안되니 배열로 돌아왔고, 행 계산 할때, 열 계산할때 둘다 동일한 배열을 사용하니 static으로 선언을 하고, 크기를 101만큼 줘야 겠다 생각했다.

-> int 형 배열은 초기화 했을때 0으로 채워지고, 100까지 넣어야하니 101개의 크기라 생각했다.

2. map을 쓸건데 정렬을 어떻게 하지?

2-1. Comparator & Comparable

자바에서의 방법을 사용하려니 답이 나오지 않았음... 사용하고 싶으면 내가 hashmap을 상속 받아 새로운 class를 만드는 방식인데 굳이...? 라는 생각에 PASS

2-2. Map.EntrySet

List<Map.EntrySet>을 사용하면 내가 원하는 대로
Comparator의 Compare를 오버라이드 해서 빈도수 대로 정렬 -> 숫자 크기대로 정렬 이 가능하길래 오버라이드해서 빈도수 대로 정렬 -> 숫자 크기대로 정렬하는 방식을 선택했다.

풀이

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

public class BOJ17140 {
    static int [][] map =new int[101][101]; //100번째를 초과하는 줄은 무시하므로.
    static int r,c,k,count=0;
    static int max_r=3, max_c=3; //가로 세로 제한 처음엔 3*3 으로 고정 값이니
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        r = Integer.parseInt(st.nextToken())-1; // 인덱스가 1부터 시작하므로 -1
        c = Integer.parseInt(st.nextToken())-1; // 인덱스가 1부터 시작하므로 -1
        k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine()," ");
            map[i][0]=Integer.parseInt(st.nextToken());
            map[i][1]=Integer.parseInt(st.nextToken());
            map[i][2]=Integer.parseInt(st.nextToken());
        }
        
// 입력 끝!
// 초 찾기
        while(map[r][c]!=k){ //만약 값이 맞으면 탈출
            count++;
            if(max_r>=max_c)//가로가 세로보다 같거나 긴경우
                map=R_cal();
            else            //세로가 긴경우
                map=C_cal();
            if(count>100)break; //100회가 넘으면
        }
        if(count<=100) //100회 미만이면
            System.out.println(count);
        else
            System.out.println(-1);
    }
    static int[][] R_cal(){
        int[][] arr = new int[101][101];    //값을 집어 넣기 위한 임시 저장소
        for (int i=0; i<101; i++) {
            if(i==max_r) break;                                 //최대  가로 수면 탈출
            Map<Integer,Integer> temp = new TreeMap<>();        // 빈도수 세기 위한 map

            for (int j =0; j<101; j++) {
                int val = map[i][j];
                temp.put(val,temp.getOrDefault(val,0)+1); // 만약 아무것도 없으면 0을 가져오기
            }

            List<Map.Entry<Integer,Integer>> entryList = new LinkedList<>(temp.entrySet());
            entryList.sort(new Comparator<Map.Entry<Integer, Integer>>() {
                @Override
                public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                    if(o1.getValue()==o2.getValue())    //만약 빈도수가 동일하면
                        return o1.getKey()-o2.getKey(); //나온 숫자 오름 차순
                    else
                        return o1.getValue()- o2.getValue();    //빈도수로 오름 차순
                }
            });

            int idx =0;                             //정렬한거 집어 넣는거
            for (Map.Entry<Integer, Integer> entry : entryList) {
                if(idx>=100)break;                  // 100을 초과 하면 pass
                if(entry.getKey()==0) continue;     //idx가 0이 존재하면 pass
                arr[i][idx++] = entry.getKey();
                arr[i][idx++] = entry.getValue();
            }
            if(idx >max_c) max_c =idx;              //정렬후에 idx가 현 map의 최대 열 보다 크면 변환
        }
        return arr;
    }

    //로직은 동일 -> 열대로 정렬
    static int[][] C_cal(){
        int[][] arr = new int[101][101];
        for (int i=0; i<101; i++) {//세로 대로 진행해야 하므로
            if(i==max_c) break;
            Map<Integer,Integer> temp = new TreeMap<>();

            for (int j =0; j<101; j++) {
                int val = map[j][i];
                temp.put(val,temp.getOrDefault(val,0)+1); // 만약 아무것도 없으면 0을 가져오기
            }

            List<Map.Entry<Integer,Integer>> entryList = new LinkedList<>(temp.entrySet());
            entryList.sort(new Comparator<Map.Entry<Integer, Integer>>() {
                @Override
                public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                    if(o1.getValue()==o2.getValue())
                        return o1.getKey()-o2.getKey();
                    else
                        return o1.getValue()- o2.getValue();
                }
            });

            int idx =0;
            for (Map.Entry<Integer, Integer> entry : entryList) {
                if(idx>=100)break;
                if(entry.getKey()==0) continue;
                arr[idx++][i] = entry.getKey();
                arr[idx++][i] = entry.getValue();
            }
            if(idx >max_r) max_r =idx;
        }
        return arr;
    }
}