[백준] 17140번: 이차원 배열과 연산- 파이썬 (+한 줄로 배열 돌리기)

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

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을 출력한다.

 

풀이

구현문제로 일단 R연산부터 함수로 만들어봤다.

조금 고민을 해보니까 C연산도 R연산 함수로 수행을 할 수 있는 것을 깨달았다.

C연산을 하기 전에 배열을 뒤집고 돌린 후 연산을 하고 다시 돌리면 된다.

 

 

+) 2차원 배열 돌리기 (찾아본 팁)

rotated_array = list(map(list, zip(*array)))

 

답안 코드

from collections import defaultdict

def operate(arr):
    new_arr = []
    max_length= 0

    for row in arr:
        new_row=[]
        counts = defaultdict(list)
        numbers = set(row)

        for num in numbers:
            if num != 0:
                counts[row.count(num)].append(num)

        for c in sorted(counts):
            for number in sorted(counts[c]):
                new_row.extend([number,c])

        new_arr.append(new_row[:100])
        max_length = max(max_length, len(new_row))

    max_length = min(100, max_length)

    for row in new_arr:
        if len(row) < max_length:
            row+=[0] * (max_length - len(row))
    
    return new_arr

def solution():
    r, c, k = map(int, input().split())

    ARRAY = [list(map(int, input().split())) for _ in range(3)]

    for t in range(101):
        if r-1 < len(ARRAY) and c-1 < len(ARRAY[0]) and ARRAY[r-1][c-1] == k:
            return t

        if len(ARRAY)>=len(ARRAY[0]):
            new_arr = operate(ARRAY)
        else:
            ARRAY = list(map(list, zip(*reversed(ARRAY))))
            new_arr = list(map(list, zip(*operate(ARRAY))))
        
        ARRAY = new_arr
    return -1

print(solution())