백준 17140번 이차원 배열과 연산 :: 마이구미

이 글은 백준 알고리즘 문제 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