[파이썬 | BOJ | 17140] 이차원 배열과 연산

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

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을 넘어가는 경우에는 -1을 출력한다.

풀이

그냥 문제에서 주어진대로 구현을 해야한다.

행과 열에 대해서 따로 구분해서 처리를 해주어야 하므로, 행 및 열에 대한 각각의 리스트를 만든다.

행의 갯수가 열의 갯수보다 많거나 같은 경우에는, 각 행별로 숫자들의 갯수를 세서 문제에서 주어진대로 새로운 리스트를 만들어야 한다. 2개로 묶인 데이터를 정렬해야 하므로 lambda로 sorting 규칙을 작성하고, 정렬된 값들을 순서대로 새로운 행으로 만들어준다.

 

열에 대해서 계산하는것도 동일한 알고리즘으로 구성한 뒤, 각각의 행/열 변환이 있고나서는 항상 행과 열의 데이터를 맞춰주어야 하므로 sync 함수로 계속 동기화를 시켜준다.

 

코드로 나타내면 다음과 같다.

 

# [파이썬 | BOJ | 17140] 이차원 배열과 연산
import sys
read = sys.stdin.readline
 
def sync():
    # row에서 column으로
    if len(rows) >= len(columns):
        columns.clear()
        rangeC = len(rows[0])
        rangeR = len(rows)
 
        for c in range(rangeC):
            temp = []
            for r in range(rangeR):
                temp.append(rows[r][c])
            columns.append(temp)
    # column에서 row로
    else:
        rows.clear()
        rangeR = len(columns[0])
        rangeC = len(columns)
 
        for i in range(rangeR):
            temp = []
            for j in range(rangeC):
                temp.append(columns[j][i])
            rows.append(temp)
 
def cal():
    rangeR = len(rows)
    rangeC = len(rows[0])
    #print(rangeR, rangeC)
    # 행의개수 >= 열의 개수
    if len(rows) >= len(rows[0]):
        temps = []
        temp_maxC = -1
        for row in rows:
            row.sort()
            ttemp = []
            i = 0
            while i < rangeC:
                if row[i] == 0:
                    i += row.count(row[i])
                    continue
                ttemp.append([row[i], row.count(row[i])])
                i += row.count(row[i])
            ttemp.sort(key = lambda x: (x[1], x[0]))
            temp = []
            for t in ttemp:
                temp.append(t[0])
                temp.append(t[1])
 
            if temp_maxC < len(temp):
                temp_maxC = len(temp)
            temps.append(temp)
 
        # 남는 길이를 0으로 맞춘다.
        for temp in temps:
            temp.extend([0 for _ in range(temp_maxC-len(temp))])
 
        #rows를 새로 바꾼다.
        rows.clear()
        for temp in temps:
            rows.append(temp)        
 
        sync()
 
    # column에서 row로
    else:
        temps = []
        temp_maxR = -1
        for column in columns:
            column.sort()
            ttemp = []
            i = 0
            while i < rangeR:
                if column[i] == 0:
                    i += column.count(column[i])
                    continue
                ttemp.append([column[i], column.count(column[i])])
                i += column.count(column[i])
            ttemp.sort(key = lambda x: (x[1], x[0]))
            temp = []
            for t in ttemp:
                temp.append(t[0])
                temp.append(t[1])
            #print(temp)
 
            if temp_maxR < len(temp):
                temp_maxR = len(temp)
            temps.append(temp)
 
        # 남는 길이를 0으로 맞춘다.
        for temp in temps:
            temp.extend([0 for _ in range(temp_maxR-len(temp))])
 
        #rows를 새로 바꾼다.
        columns.clear()
        for temp in temps:
            columns.append(temp)        
 
        sync()
 
R, C, K = map(int, read().split())
rows = []
columns = []
t = 0
for _ in range(3):
    rows.append(list(map(int, read().split())))
#초기 column 복사
sync()
 
while t <= 110: #넉넉하게 잡아줌
    #print(rows)
    try:        #TC에 초기 index를 벗어나는게 존재함.
                #따라서 그냥 indexing error 무시하고 넘어감
        if rows[R-1][C-1] == K:
            break
    except IndexError:
        pass
    cal()
    t += 1
 
print(t if t <= 100 else -1)