[Python] 17140 이차원 배열과 연산

in Algorithm on 문제풀이, Simulation


17140 이차원 배열과 연산

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 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을 출력한다.

풀이

  • 먼저 row operation을 구현
    • 1) 각 row에 차례로 접근하여 원소의 개수를 구함(collections 라이브러리의 Counter함수를 사용)
    • 2) 0을 제외
    • 3) 적게 등장하는 원소부터 등장하도록 정렬함
    • 4) 최대 행길이를 찾고 나머지 행들을 0으로 채우기
    • 5) 행 또는 열의 크기가 100을 넘어가는 경우 처음 100개를 제외한 나머지를 버림
  • col operation의 경우 transpose와 row operation으로 구현 가능
    • matrix를 transpose한 후 row_operation, 다시 transpose하면 col operation과 같다.
  • while문으로 operation을 실행 한 후 주어진 (r,c)의 원소가 k이면 break 하고 operation 횟수를 출력. 100을 넘어가면 -1을 출력
from collections import Counter

r,c,k = map(int,input().split())
my_mat = [list(map(int, input().split())) for _ in range(3)]

def transpose(my_mat):
    new_mat =  [list(x) for x in zip(*my_mat)]
    return new_mat

# r연산
def row_c(my_mat):
    for i in range(len(my_mat)):
        my_mat[i].sort()
        c = Counter(my_mat[i]) # 1) 각 row에 차례로 접근하여 원소의 개수를 구함
        new_array = [x for x in c.items() if x[0] != 0] # 2) 0을 제외
        new_array.sort(key = lambda x: x[1]) # 3) 적게 등장하는 원소부터 등장하도록 정렬함 
        my_mat[i] = [y for x in new_array for y in x] # nested_list를 풀어줘야함 ex) [(2,1),(1,2)] -> [2,1,1,2]

    # 4) 최대 행길이를 찾고 나머지 행들을 0으로 채우기
    max_len = max([len(x) for x in my_mat])
    for i in range(len(my_mat)):
        if len(my_mat[i]) < max_len:
            my_mat[i] += [0]*(max_len - len(my_mat[i]))

    # 5) 행 또는 열의 크기가 100을 넘어가는 경우 처음 100개를 제외한 나머지를 버림 
    my_mat = my_mat[:100]
    my_mat = [x[:100] for x in my_mat]

    return my_mat

# c연산
def col_c(my_mat):
    my_mat = transpose(my_mat)
    my_mat = row_c(my_mat)
    my_mat = transpose(my_mat)

    # 행 또는 열의 크기가 100을 넘어가는 경우 처음 100개를 제외한 나머지는 버린다. 
    my_mat = my_mat[:100]
    my_mat = [x[:100] for x in my_mat]

    return my_mat

i = 0
while True:
    if len(my_mat) >= r and len(my_mat[0]) >= c:
        if my_mat[r-1][c-1] == k:
            print(i)
            break

    nrow = len(my_mat)
    ncol = len(my_mat[0])

    if nrow >= ncol:
        my_mat = row_c(my_mat)
    else:
        my_mat = col_c(my_mat)

    i += 1

    if i == 101:
        print(-1)
        break