[BOJ] 삼성 sw 역량 테스트 :: 17140번 이차원 배열과 연산 (java)

BOJ 17140번 이차원 배열과 연산 문제 자바(java) 풀이

• 랭크 : 골드4
• 백준 17140번 이차원 배열과 연산

 

문제 정리

1. 크기가 3x3인 배열 A
2. 1초마다 배열에 연산 적용
3. R연산: 배열 A의 모든 행에 대해서 정렬을 수행. 행 >= 열
4. C연산: 배열 A의 모든 열에 대해서 정렬을 수행. 행 < 열
5. 각각의 수가 몇 번 나왔는지 알아야 함. 수의 등장 횟수가 커지는 순으로 정렬
6. 그러한 것이 여러가지이면 수가 커지는 순으로 정렬
7. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저
8. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변함
9. C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변함
10. 행 또는 열의 크기가 커진 곳에는 0이 채워진다
11. 수를 정렬할 때 0은 무시함
12. 행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.
13. A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간 구하기
14. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력

문제 풀이

문제에 주어진 그대로 구현하면 된다.
푸는데 2시간 정도 걸렸다....
이대로면 1솔인데 ㅠㅠㅠ
어렵진 않지만 index가지고 장난치는건 넘 헷갈린다.
처음에 문제를 이해하고 어떻게 풀지 고민하는데 시간이 오래걸렸다.

1. 행의 길이와 열의 길이에 따라 R/C 연산을 수행한다.
2. time을 증가시킨다.
3. arr[r-1][c-1]의 값이 k인지 확인하여 맞다면 실행을 멈추고 time을 출력한다.
4. 그렇지 않다면 반복한다.
5. 그러다가 time이 100을 넘어가면 조건에 의해 -1을 출력하도록 한다.
   
   
   

R 연산

1. 행 기준으로 숫자를 보며 map에 넣는다.(0은 무시)
2. map의 entry를 list로 만든다.
3. collections.sort에 comparator를 구현하여 정렬한다. 개수 기준 정렬하고 같을 경우 key 기준 정렬한다. (오름차순)
4. entry 크기의 2배만큼 새로운 배열을 만든다(entry가 (key, value) 이므로)
5. maxLen의 크기를 update한다(가장 큰 행을 기준으로 모든 행의 크기가 변하기 때문)
6. maxLen이 100을 넘는 경우에는 100으로 해준다.(행또는 열의 크기가 100이 넘는 경우 그 뒤는 무시)
7. 새로운 행 배열에 값을 key, value 차례차례 담는다.
8. 그리고 가장 큰 행 기준 0을 채우기 위해 행의 길이가 maxLen만큼 새로운 행을 만들고 거기에 기존 배열 값을 담는다(새로 만들시 0으로 초기화 되기 때문
   
   
   

C 연산

C 연산은 R과 동일하게 진행하고 Transpose 시키면 된다.

1. 0 붙여 넣기 까지의 과정은 동일하다.
2. 행의 길이는 기존 열의 길이가 되고 열의 길이는 maxLen이 된다.
3. 그리고 이중 for문을 돌며 반전시키면 된다.
4. 그리고 반전이 되었으므로 행의 길이와 열의 길이를 바꿔준다.
   
   

코드가 조금 길지만 주어진 그대로 구현하여 2번만에 성공하였다.

백준 17140번 이차원 배열과 연산 자바 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
 
 
class Main {
    static int r, c, k;
    static int[][] arr;
    static int rowNum, colNum;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        r = Integer.parseInt(temp[0]);
        c = Integer.parseInt(temp[1]);
        k = Integer.parseInt(temp[2]);
        
        arr = new int[3][3];
        rowNum = 3;
        colNum = 3;
        for(int i=0; i<3; i++) {
            temp = br.readLine().split(" ");
            for(int j=0; j<3; j++) {
                arr[i][j] = Integer.parseInt(temp[j]);
            }
        }
        
        int time = 0;
        while(true) {
            if(r-1 < rowNum && c-1 < colNum) {
                if(arr[r-1][c-1] == k) break;                
            }
            if(time > 100) break;
 
            // R 연산
            if(rowNum >= colNum) {
                arr = rOperation();
            }
            else {
                // C 연산
                arr = cOperation();
            }
            time++;
        }
        
        if(time > 100) System.out.println(-1);
        else System.out.println(time);
    }
    
    // 각각 수가 몇개 있는지 확인
    public static int[][] rOperation() {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[][] newArr = new int[rowNum][];
        int maxLen = 0;
        
        for(int i=0; i<rowNum; i++) {
            for(int j=0; j<colNum; j++) {
                int num = arr[i][j];
                if(num != 0) {
                    if(map.containsKey(num)) {
                        map.put(num, map.get(num)+1);
                    }
                    else {
                        map.put(num, 1);
                    }
                    
                }                
            }
            
 
            // 새로운 배열 만들기전 정렬
            List<Entry<Integer, Integer>> list_entries = new ArrayList<Entry<Integer, Integer>>(map.entrySet());
            
            // 개수 기준 오름차순 정렬
            Collections.sort(list_entries, new Comparator<Entry<Integer, Integer>>() {
                // compare로 값을 비교
                public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) {
                    // 오름 차순 정렬
                    if(obj1.getValue().compareTo(obj2.getValue()) > 0) {
                        return 1;
                    }
                    else if(obj1.getValue().compareTo(obj2.getValue()) < 0) {
                        return -1;
                    }
                    else {
                        return obj1.getKey().compareTo(obj2.getKey());                        
                    }
                }
            });
            
            newArr[i] = new int[list_entries.size()*2];
            int idx = 0;
            int size = list_entries.size();
            maxLen = maxLen < size*2 ? size*2 : maxLen;
            
            // 열이 100을 넘는 경우, 100까지만
            maxLen = maxLen > 100 ? 100 : maxLen;
            
            for(int k=0; k<size; k++) {
                newArr[i][idx++] = list_entries.get(k).getKey();
                newArr[i][idx++] = list_entries.get(k).getValue();
                
                if(idx == 100) break;
            }
            
            map.clear();
        }
              
        colNum = maxLen;
        // 0 붙여 넣기
        for(int i=0; i<rowNum; i++) {
            int[] temp = new int[maxLen];
            int[] row;
            
            if(maxLen > newArr[i].length) {
                row = Arrays.copyOf(newArr[i], newArr[i].length);
                for(int j=0; j<row.length; j++) {
                    temp[j] = row[j];
                }
                newArr[i] = temp;                
            }
        }
        
        return newArr;
    }
    
    public static int[][] cOperation() {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[][] newArr = new int[colNum][];
        int maxLen = 0;
        
        for(int i=0; i<colNum; i++) {
            for(int j=0; j<rowNum; j++) {
                int num = arr[j][i];
                if(num != 0) {
                    if(map.containsKey(num)) {
                        map.put(num, map.get(num)+1);
                    }
                    else {
                        map.put(num, 1);
                    }        
                }
            }
            
            // 새로운 배열 만들기전 정렬
            List<Entry<Integer, Integer>> list_entries = new ArrayList<Entry<Integer, Integer>>(map.entrySet());
            
            // 개수 기준 오름차순 정렬
            Collections.sort(list_entries, new Comparator<Entry<Integer, Integer>>() {
                // compare로 값을 비교
                public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) {
                    // 오름 차순 정렬
                    if(obj1.getValue().compareTo(obj2.getValue()) > 0) {
                        return 1;
                    }
                    else if(obj1.getValue().compareTo(obj2.getValue()) < 0) {
                        return -1;
                    }
                    else {
                        return obj1.getKey().compareTo(obj2.getKey());                        
                    }
                }
            });
            
            newArr[i] = new int[list_entries.size()*2];
            int idx = 0;
            int size = list_entries.size();
            maxLen = maxLen < size*2 ? size*2 : maxLen;
            
            // 열이 100을 넘는 경우, 100까지만
            maxLen = maxLen > 100 ? 100 : maxLen;
            
            for(int k=0; k<size; k++) {
                newArr[i][idx++] = list_entries.get(k).getKey();
                newArr[i][idx++] = list_entries.get(k).getValue();
                
                if(idx == 100) break;
            }
            
            map.clear();
        }
        
        rowNum = colNum;
        colNum = maxLen;
        // 0 붙여 넣기
        for(int i=0; i<rowNum; i++) {
            int[] temp = new int[maxLen];
            int[] row;
            
            if(maxLen > newArr[i].length) {
                row = Arrays.copyOf(newArr[i], newArr[i].length);
                for(int j=0; j<row.length; j++) {
                    temp[j] = row[j];
                }
                newArr[i] = temp;                
            }
        }
        
        // 반전 시키기
        int[][] returnArr = new int[colNum][rowNum];
        
        for(int i=0; i<colNum; i++) {
            for(int j=0; j<rowNum; j++) {
                returnArr[i][j] = newArr[j][i];
            }
        }
 
        int temp = rowNum;
        rowNum = colNum;
        colNum = temp;
        
        return returnArr;
    }
}