• 백준 17140번 이차원 배열과 연산 :: 마이구미
    알고리즘 풀이/스택, 큐 2019. 6. 9. 00:36
    반응형
    이 글은 백준 알고리즘 문제 17140번 "이차원 배열과 연산" 을 풀이한다.
    삼성 SW 역량 테스트 문제이다.
    큐와 정렬을 이용해서 문제를 해결한다.
    문제 링크 - https://www.acmicpc.net/problem/17140

     

    크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.

    • R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
    • C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

    한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

    예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

    정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 커질 수 있다. R 연산이 적용된 경우에는 행의 크기가 가장 큰 행을 기준으로 모든 행의 크기가 커지고, C 연산이 적용된 경우에는 열의 크기가 가장 큰 열을 기준으로 모든 열의 크기가 커진다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

    행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

    배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

     


     

    문제 이해가 잘 되지 않는다면, 문제 힌트를 참고하면 이해하기 쉽다.

    문제가 원하는 것은 다음과 같다.

     

    1. R 연산과 C 연산으로 구분되어 실행된다.
    2. 연산 결과에 대한 정렬의 기준은 수의 등장 횟수가 커지는 순이고, 여러개라면 수가 커지는 순으로 정렬한다.
    3. 정렬된 결과를 다시 배열에 넣을 때는 수부터 먼저 넣는다.
    4. 행 또는 열의 크기가 100을 넘으면 100 초과한 값들은 버린다.

     

    각각이 의미하는 것은 다음과 같다.

    1번은 행의 개수 >= 열의 개수라면 R 연산, 그렇지 않으면 C 연산을 실행한다.

    2번이 의미하는 것은 다음과 같다.

     

    1 2 1 1 3 4 4
    => 1의 개수 => 3, 2의 개수 => 2, 3의 개수 => 1, 4의 개수 2개

     

    위 결과를 수의 등장 횟수를 기준으로 정렬한다면, 3 4 2 1 또는 3 2 4 1 로 나타낼 수 있다.

    4, 2 의 경우 등장 횟수가 동일하기에, 수가 커지는 순으로 정렬해주어야한다.

    올바른 결과는 3, 2, 4, 1 순서이다.

    그리고 3번을 반영한 최종값은 다음과 같다.

     

     

    4번은 연산을 실행하고 난 후의 결과값에서 100개를 넘는 값들을 버리면 된다.

    연산을 실행하는 도중에 100개를 초과했다고 중단하는 것이 아니라, 모든 결과가 실행된 후의 결과를 버린다.

     

    사실 위 요구사항이 의미하는 것을 이해했다면, 코드 구현에 있어서 큰 어려움은 없다.

    각 행 또는 열에 있는 모든 수에 대해 횟수를 체크한 후에, 정렬을 해주면 된다.

     

    for (int i = 1; i <= rn; i++) {
        for (int j = 1; j <= cn; j++) {
             cnt[input[i][j]]++;
        }
        sort();
    }

     

    sort() 를 통해 정렬된 결과를 우리는 다시 배열에 넣어주는 행위를 하면 된다.

    본인은 정렬을 위해 우선순위 큐를 사용했다.

     

    PriorityQueue<Item> sort() {
         PriorityQueue<Item> q = new PriorityQueue<Item>(new ComparatorSort()); // 우선순위 정렬 기준 오버라이딩
         for (int i = 1; i <= 100; i++) {
             if (cnt[i] > 0) {
                 q.add(new Item(i, cnt[i]));
             }
         }
         return q;
    }

     

    사실 이 문제는 입력 값이 크지 않았기 때문에, 시간 초과 걱정은 하지 않았다.

    정렬을 커스텀할 수만 있다면, 크게 어렵지 않다.

    자세한 것은 전체 코드를 통해 이해하길 바란다.

     

    Github - https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/17140.java

    반응형

    댓글

Designed by Tistory.