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

문제 보기

 

구현, 시뮬레이션 문제이다.

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력하면 된다.

 

최소 시간?

연산의 순서가 정해져 있기 때문에 최소라는 말은 큰 의미가 없다. A[r][c] 값을  k로 만들 수 있는 특별한 연산 방법이 있는 것이 아니라, 연산의 순서에 따라 진행하면서 A[r][c]의 값이 k인지 주기적으로 확인하면 된다.

 

배열의 크기

연산을 진행하다 보면 행 또는 열의 크기가 변한다. 하지만 행 또는 열의 크기가 100을 넘어가는 경우는 의미없는 값이기 때문에 처음부터 배열 크기를 100 x 100으로 선언하면 행 또는 열의 크기 변화를 신경 쓸 필요가 없다.

 

행과 열의 크기 비교

행과 열의 크기 변화는 신경 쓸 필요가 없지만 행의 최대 크기와 열의 최대 크기는 알아야 한다. 최대 크기에 따라 수행하는 연산이 다르기 때문이다.  최대 행과 열 크기는 아래 방법으로 구하였다.

def find_col_index(arr):  # 최대 열 크기 계산
    index = 0
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[i][j] == 0:
                index = max(index, j)
                break
    return index


def find_row_index(arr):  # 최대 행 크기 계산
    index = 0
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[j][i] == 0:
                index = max(index, j)
                break
    return index

 

R 연산 vs C 연산 

R 연산과 C 연산의 알고리즘 로직은 아래와 동일하다.

1. 0을 제외한 수의 갯수를 파악한다. -> Counter 함수 사용

2. (수, 등장 횟수) 순으로 정렬하고, 정렬된 결과를 100개까지만 넣는다.

 

전체적인 알고리즘 로직은 아래와 같습니다.

1. 행과 열의 크기를 비교한다.

2. 연산을 수행한다.

3. A[r][c] 값을 k와 비교한다

 

코드

from collections import Counter


def r_operation(arr):  # R 연산
    for i in range(len(arr)):
        temp = []
        for j in range(len(arr[i])):
            if arr[i][j] != 0:
                temp.append(arr[i][j])

        counter = Counter(temp)
        temp = []
        for key in counter.keys():
            temp.append((key, counter[key]))
        temp = sorted(temp, key=lambda x: (x[1], x[0]))
        for j in range(50):
            if j < len(temp):
                arr[i][j * 2] = temp[j][0]
                arr[i][j * 2 + 1] = temp[j][1]
            else:
                arr[i][j * 2] = 0
                arr[i][j * 2 + 1] = 0
    return arr


def c_operation(arr):  # C 연산
    for i in range(len(arr)):
        temp = []
        for j in range(len(arr)):
            if arr[j][i] != 0:
                temp.append(arr[j][i])

        counter = Counter(temp)
        sort_arr = []
        for key in counter.keys():
            sort_arr.append((key, counter[key]))

        sort_arr = sorted(sort_arr, key=lambda x: (x[1], x[0]))
        for j in range(50):
            if j < len(sort_arr):
                arr[j * 2][i] = sort_arr[j][0]
                arr[j * 2 + 1][i] = sort_arr[j][1]
            else:
                arr[j * 2][i] = 0
                arr[j * 2 + 1][i] = 0
    return arr


def find_col_index(arr):
    index = 0
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[i][j] == 0:
                index = max(index, j)
                break
    return index


def find_row_index(arr):
    index = 0
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[j][i] == 0:
                index = max(index, j)
                break
    return index


if __name__ == "__main__":
    R, C, K = map(int, input().split())
    array = [[0] * 101 for _ in range(101)]
    for i in range(3):
        a, b, c = map(int, input().split())
        array[i][0], array[i][1], array[i][2] = a, b, c

    flag = True
    for i in range(0, 101):
        if array[R - 1][C - 1] == K:
            print(i)
            flag = False
            break
        if find_row_index(array) >= find_col_index(array):
            array = r_operation(array)
        else:
            array = c_operation(array)

    if flag:
        print(-1)