프로그래밍/알고리즘

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

고등어찌짐 2022. 9. 21. 20:04

 

각 열마다 소팅하는 함수를 만든 후, 배열을 transpose 해서 열에 대해서도 같은 함수로 계산

 

def get_size(arr):
    row_n = len(arr)
    col_n = len(arr[0])
    return row_n, col_n


def count_element(row):
    max_num = max(row)
    cnt = [0 for _ in range(max_num + 1)]
    for r in row:
        cnt[r] += 1
    return cnt


def sorting_func(arr):
    new_arr = []
    row_size = 0
    
    # 소팅은 행마다 이루어짐
    for row in arr:
        cnt_dict = {}
        cnt = count_element(row)
        for i, v in enumerate(cnt):
            if v != 0 and i != 0:
                # 등장횟수, 수
                if v not in cnt_dict:
                    cnt_dict[v] = [i]
                else:
                    cnt_dict[v].append(i)

        key_sort = sorted(cnt_dict)
        for k, v in cnt_dict.items():
            if len(v) > 1:
                cnt_dict[k] = sorted(v)

        # 한 줄로 다시 만든다
        new_row = []
        for ks in key_sort:
            elements = cnt_dict.get(ks)
            for e in elements:
                new_row.append(e)
                new_row.append(ks)

        row_size = max(row_size, len(new_row))
        new_arr.append(new_row)

    # 하나의 배열로 다시 생성
    for i, nr in enumerate(new_arr):
        diff = row_size-len(nr)
        if diff > 0:
            for _ in range(diff):
                nr.append(0)
            new_arr[i] = nr

    return new_arr


def transpose(arr):
    rc, cc = get_size(arr)
    new_arr = [[0 for _ in range(rc)] for _ in range(cc)]
    for i in range(cc):
        for j in range(rc):
            new_arr[i][j] = arr[j][i]
    return new_arr


if __name__ == '__main__':
    r, c, k = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(3)]
    res = 0
    while 1:
        if res > 100 :
            res = -1
            break

        # 행, 렬 개수 체크
        row_num, col_num = get_size(board)
        if 0 <= (r-1) < row_num and 0 <= c-1 < col_num and board[r - 1][c - 1] == k:
            break

        # 행 >= 열 : R
        if row_num >= col_num:
            board = sorting_func(board)

        # 열 > 행 : C
        elif col_num > row_num:
            t_board = transpose(board)
            t_board = sorting_func(t_board)
            board = transpose(t_board)

        res += 1

    print(res)

 

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

 

17140번: 이차원 배열과 연산

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

www.acmicpc.net