[BOJ] 17140.이차원배열과 연산 (Python)

 

17140번: 이차원 배열과 연산

 

해당 문제는 r행 c열의 값이 k가 되기 위한 연산 최소 시간을 출력하는 문제입니다.

 

처음에 크기가 3x3인 배열 A가 주어지며, 1초마다 다음 배열 연산이 적용됩니다.

• R 연산 : 행의 개수 >= 열의 개수인 경우, 모든 행에 대해 정렬 수행
• C 연산 : 행의 개수 < 열의 개수인 경우, 모든 열에 대해 정렬 수행

정렬을 할 때는 숫자의 개수, 숫자 순서로 합니다.

예를 들어, 처음에 주어진 배열이 [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열이 k일 때 시간을 출력하면 되는데,

실제로는 A[r-1][c-1]이 k일 때 시간을 출력하면 됩니다. 그러나 100초가 넘어가면 -1을 출력합니다.

그리고 r행과 c열의 길이는 100을 넘어갈 수 없으며, 100이 넘는 경우 처음 100개를 제외한 나머지는 버립니다.

 

저는 이 문제를 다음과 같은 방식으로 풀었습니다.

1. R 연산을 기준으로 연산 함수를 생성한다.
2. R 연산의 경우, 연산 함수를 그대로 실행한다.
   C 연산의 경우, 배열을 전치시켜 연산 함수를 실행하며 수행 후 다시 배열을 전치시켜준다.
3. A[r-1][c-1] == k 인 경우 시간을 출력한다.
4. 100초가 지나도 r행 c열이 k가 되지 않으면 -1을 출력한다.

# 이차원 배열과 연산
import sys

# 연산함수
# A : NxN 배열, L : 행의 길이 (칼럼 개수)
def operation(A, L) :
    for idx, row in enumerate(A) :
        temp = []
        for n in set(row) : # 행의 중복을 제거한 후
            if n : # 0이 아닌 숫자면
                temp.append((n, row.count(n))) # 해당 숫자에 대한 값을 세어줌
        temp = sorted(temp, key = lambda x : (x[1], x[0])) # 개수, 숫자 순서로 정렬
        templen = len(temp)
        if templen > 50 : templen = 50 # 숫자의 개수는 100을 넘어가면 안됨
        L = max(L, templen * 2) # 행의 길이를 최대로 바꿔줌
        A[idx] = [] # A의 idx행 초기화
        for i in range(templen) : # A의 idx행 재구성
            A[idx].append(temp[i][0])
            A[idx].append(temp[i][1])
    
    # 최대 길이만큼 0 채우기
    for idx, row in enumerate(A) :
        for _ in range(L-len(row)) :
            A[idx].append(0)
    
    return A, L

if __name__=='__main__' :
    r, c, k = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(3)]

    rlen, clen = 3, 3
    for time in range(101) :
        if r <= rlen and c <= clen and A[r-1][c-1] == k :
            print(time)
            break
        if rlen >= clen : # R연산
            A, clen = operation(A, clen)
        else : # C연산
            A, rlen = operation(list(zip(*A)), rlen) # 행과 열을 전치시켜 함수를 실행한다.
            A = list(zip(*A)) # 행과 열을 원상태로 바꾼다.
    else : # 100초 동안 r행 c열이 k가 아닌 경우
        print(-1)