[BOJ] 백준 17140 이차원 배열과 연산

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

1 2 1

1 2 1

2 1 3

3 3 3

 

 Output 

1

 

가장 처음에는 행의 개수 ≥ 열의 개수 이므로 R 연산 적용

① 행의 경우) 

- 『1』 이  두 번 / 『2』가 한 번으로 나타났으므로 '나타난 횟수'를 기준으로 괄호 구성이 정렬됩니다.

    그래서 위와 같이 (『2』, 1) → (『1』, 2)로 정렬되었습니다.

- '나타난 횟수'가 동일할 때는 숫자의 크기(순서)로 정렬.

 

② 행의 경우) 

- 『1』 이  두 번 / 『2』가 한 번으로 나타났으므로 '나타난 횟수'를 기준으로 괄호 구성이 정렬됩니다.

    그래서 위와 같이 (『2』, 1) → (『1』, 2)로 정렬.

- '나타난 횟수'가 동일할 때는 숫자의 크기(순서)로 정렬됩니다.

 

③행의 경우

    『2』, 『1』,  『3』  모두 나타난 횟수는 한 번으로 동일하기 때문에

    → (『1』, 1) - (『2』, 1) - (『3』, 1)으로 오름차순으로 정렬

 

②행을 기준으로 나머지 행에는 『0』으로 채워집니다.

2 1 1 2 0 0

1 1 2 1 3 1

3 3 0 0 0 0

 

* 『0』은 단순히 자리를 채워주는 것이기에 연산 대상은 아닙니다.

따라서, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 동일.

 

행의 개수 < 열의 개수이므로 C 연산 적용

1 3 1 1 3 1

1 1 1 1 1 1

2 1 2 2 0 0

1 2 1 1 0 0

3 0 0 0 0 0

1 0 0 0 0 0

1열: (1, 1) - (2, 1) - (3, 1)    ← 나타난 횟수가 동일, 숫자의 크기로 정렬

2열: (3, 1) - (1, 2)    ← 나타난 횟수로 정렬

3열: (1, 1) - (2, 1)    ← 나타난 횟수가 동일, 숫자의 크기로 정렬

4열: (1, 1) - (2, 1)    ← 나타난 횟수가 동일, 숫자의 크기로 정렬

5열: (3, 1)

6열: (1, 1)

 

구현 순서

- 현재 배열이 R 연산인지, C 연산을 해야 하는지 확인

    (행R, 열C의 크기로 판단  ← 처음에는 3*3 이므로 R 연산부터 시작)

- 배열의 크기는 100 x 100을 넘지 않는다.

   정렬 후 크기가 100개 넘은 지점은 버리고, 부족하면 『0』으로 채웁니다.

- A[r][c] = k 일 때까지 반복

  연산을 100번내로 하지 못하면 『-1』 출력

    

숫자가 나타난 횟수를 기준으로 정렬하되, 

나타난 횟수가 동일하면 숫자의 크기로 정렬

→ 우선 순위 큐로 구현

---

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    
    static int R=3, C=3;
    static int[][] arr;
    static int answer = -1;
    
    static class Vertex implements Comparable<Vertex>{
        int val;
        int cnt;
        
        public Vertex(int val, int cnt) {
            this.val = val;
            this.cnt = cnt;
        }
        
        @Override
        public int compareTo(Vertex target) {
            // 나타난 횟수가  작으면 먼저 오도록
            if(this.cnt < target.cnt) return -1;
            else if (this.cnt > target.cnt) return 1;
            // 나타난 횟수가 동일하면 숫자 크기 순으로
            else return (this.val <= target.val) ? -1 : 1;
            
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int r = Integer.parseInt(sc.next());
        int c = Integer.parseInt(sc.next());
        
        int k = Integer.parseInt(sc.next());
        
        // 100 x 100
        arr = new int[100][100];
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                arr[i][j] = Integer.parseInt(sc.next());
            }
        }
        
        // 100번 시도해서 실패하면 『-1』 출력
        for(int tryCnt = 0; tryCnt <= 100; tryCnt++) {
            if(arr[r-1][c-1] == k) {
                answer = tryCnt;
                break;
            }
            // R 연산
            if(R >= C) rOperation();
            
            
            // C 연산
            else cOperation();


            // 디버깅 시 주석해제
            // printArr();  
            
        }


        System.out.println(answer);        
    }


    private static void rOperation() {
        Map<Integer, Integer> map;
        PriorityQueue<Vertex> pq;
        int[][] temp = new int[100][100];
        int tempC = 0;

        // 모든 행에 대해
        for(int i=0; i<R; i++) {
            map = new HashMap<Integer, Integer>();
            for(int j=0; j<C; j++) {
                // 0 이면 연산 대상 X
                if (arr[i][j] == 0) continue;
                // 등장 횟수 count
                if(map.get(arr[i][j]) == null) map.put(arr[i][j], 1);
                else map.put(arr[i][j], map.get(arr[i][j]) + 1);
            }
            
            pq = new PriorityQueue<>();
            // 등장횟수가 많고, 숫자 크기 순으로 정렬
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                pq.add(new Vertex(entry.getKey(), entry.getValue()));
            }
            
            // tempC 크기 갱신
            tempC = (tempC < pq.size() * 2) ? pq.size() * 2 : tempC;
            if (tempC > 100) tempC = 100;
            
            // 해당 열을 재배치
            int col = 0;
            while(!pq.isEmpty()) {
                Vertex v = pq.poll();
                temp[i][col] = v.val;
                temp[i][col + 1] = v.cnt;
                
                col = col + 2;
                if(col >= 100) {
                    // 100개 이상이면 나머지는 버려준다.
                    break;
                }
            }
            
            pq.clear();
            map.clear();
        }
        
        C = tempC;
        deepCopy(temp);
    }
    
    private static void deepCopy(int[][] temp) {
        arr = new int[100][100];
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                System.arraycopy(temp[i], 0, arr[i], 0, temp[i].length);
            }
        }
        
    }


    private static void cOperation() {
        Map<Integer, Integer> map;
        PriorityQueue<Vertex> pq;
        int[][] temp = new int[100][100];
        int tempR = 0; // 연산 시작 시 열의 개수
        // 모든 행에 대해
        for(int j=0; j<C; j++) {
            map = new HashMap<Integer, Integer>();
            for(int i=0; i<R; i++) {
                // 0 이면 연산 대상 X
                if (arr[i][j] == 0) continue;
                // 등장 횟수 count
                if(map.get(arr[i][j]) == null) map.put(arr[i][j], 1);
                else map.put(arr[i][j], map.get(arr[i][j]) + 1);
            }
            
            pq = new PriorityQueue<>();
            // 등장횟수가 많고, 숫자 크기 순으로 정렬
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                pq.add(new Vertex(entry.getKey(), entry.getValue()));
            }
            
            // tempR 크기 갱신
            tempR = (tempR < pq.size() * 2) ? pq.size() * 2 : tempR;
            if (tempR > 100) tempR = 100;
            
            // 해당 열을 재배치
            int row = 0;
            while(!pq.isEmpty()) {
                Vertex v = pq.poll();
                temp[row][j] = v.val;
                temp[row+1][j] = v.cnt;
                
                row = row + 2;
                if(row >= 100) {
                    // 100개 이상이면 나머지는 버려준다.
                    break;
                }
            }
            
            pq.clear();
            map.clear();
        }
        
        R = tempR;
        deepCopy(temp);
    }
    
    private static void printArr() {
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                System.out.printf("%2d ", arr[i][j]);
            }
            System.out.println();
        }    
    }
}