[문제 바로가기] 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가 되기 위한 최소 시간을 구해보자.
입력
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
출력
A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.
💡 문제 풀이
주어진 문제의 내용을 그대로 구현하면 되는 '시뮬레이션(구현)'유형이 문제다.
행, 열의 크기에 따라 연산의 방향이 달라지는데, 파이썬의 경우 zip(*배열) 을 사용하면 전치행렬(행과 열이 바뀌는)을 쉽게 구할 수 있다.
숫자와, 그 숫자의 개수에 따라 정렬하는 부분은 숫자마다 (숫자, 개수)의 쌍을 미리 구해놓고 lambda를 이용하여 정렬하였다.
마지막으로 가장 큰 행(또는 열)을 기준으로 모든 행(또는 열)의 크기를 맞춰주면 된다.
※주의할 점 : A[r][c]가 k값이 나올 때 까지 연산을 수행하는데, 연산을 진행하다보면 배열 A의 크기가 변하면서 (r, c)에 해당하는 원소가 없어 IndexError가 발생할 수 있다. → 예외처리 필요
코드는 다음과 같다.
import sys
r, c, k = map(int, input().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(3)]
def calculate(matrix, dir): # 배열A의 연산
new_matrix, length = [], 0 # 연산 후 반환할 행렬 / 최대 길이의 행(또는 열)
for row in matrix:
num_cnt, new_row = [], [] # (숫자, 개수)를 담을 배열 / 연산 후의 행(또는 열)을 담을 배열
for num in set(row): # 각 숫자에 대해서 개수를 파악
if num == 0: continue # 0일 경우 continue
cnt = row.count(num)
num_cnt.append((num, cnt))
num_cnt = sorted(num_cnt, key=lambda x:[x[1], x[0]]) # 정렬
for num, cnt in num_cnt:
new_row += [num, cnt]
new_matrix.append(new_row)
length = max(length, len(new_row))
for row in new_matrix: # 가장 긴 행(또는 열)의 크기에 맞춰 0 추가
row += [0] * (length - len(row))
if len(row) > 100: row = row[:100] # 크기가 100이 넘어가면 슬라이싱
return list(zip(*new_matrix)) if dir == 'C' else new_matrix
time = 0
while True:
if time > 100: time = -1; break # 시간이 100이 넘으면 break
if 0 <= r-1 < len(matrix) and 0 <= c-1 < len(matrix[0]) and matrix[r-1][c-1] == k: break # (r, c)의 값이 k와 일치하면 break
if len(matrix) >= len(matrix[0]): # 행의 개수 >= 열의 개수
matrix = calculate(matrix, 'R')
else:
matrix = calculate(list(zip(*matrix)), 'C')
time += 1
print(time)
