백준 온라인 저지, 구현 / 17140번: 이차원배열과연산 (파이썬 / , 백준 골드문제, 삼성 SW 기출문제)

문제

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

제한

예제 입력 1

1 2 2
1 2 1
2 1 3
3 3 3

예제 출력 1

0

예제 입력 2

1 2 1
1 2 1
2 1 3
3 3 3

예제 출력 2

1

예제 입력 3

1 2 3
1 2 1
2 1 3
3 3 3

예제 출력 3

2

예제 입력 4

1 2 4
1 2 1
2 1 3
3 3 3

예제 출력 4

52

예제 입력 5

1 2 5
1 2 1
2 1 3
3 3 3

예제 출력 5

-1

예제 입력 6

3 3 3
1 1 1
1 1 1
1 1 1

예제 출력 6

2

힌트

배열 A의 초기값이 아래와 같은 경우를 생각해보자.

1 2 1
2 1 3
3 3 3

가장 처음에는 행의 개수 ≥ 열의 개수 이기 때문에, R 연산이 적용된다. 편의상 정렬 중간 단계는 (수, 수의 등장 횟수)로 표현한다.

1 2 1 → (2, 1), (1, 2)         → 2 1 1 2
2 1 3 → (1, 1), (2, 1), (3, 1) → 1 1 2 1 3 1
3 3 3 → (3, 3)                 → 3 3

크기가 가장 큰 행은 2번 행이고, 나머지 행의 뒤에 0을 붙여야 한다.

2 1 1 2 0 0
1 1 2 1 3 1
3 3 0 0 0 0

다음에 적용되는 연산은 행의 개수 < 열의 개수이기 때문에 C 연산이다. 

1 3 1 1 3 1
1 1 1 1 1 1
2 1 2 2 0 0
1 2 1 1 0 0
3 0 0 0 0 0
1 0 0 0 0 0

연산이 적용된 결과는 위와 같다.

접근 방법

- 0. A[r][c] = k인지 확인하고 맞으면 연산횟수를 출력한다.
- 1. 딕셔너리를 통해 각 연산에 따라 행 또는 열의 값을 키로 하고, 그 값의 등장횟수를 밸류로 저장한다.
- 2. 이후 딕셔너리의 items를 하나씩 출력한 뒤, 리스트 형태로 이를 저장한다.
- 3. 리스트 내에서 수의 등장횟수와 수를 통해 오름차순으로 정렬한다.
- 4. 모든 행과 열에 대해 최대 길이만큼 배열의 크기를 맞춘다.
- 5. 이를 모든 행과 열에 대해서 A[r][c]가 k가 될 때까지 반복한다.

코드

# https://www.acmicpc.net/problem/17140
# 접근방법
# 0. A[r][c] = k인지 확인하고 맞으면 연산횟수를 출력한다.
# 1. 딕셔너리를 통해 각 연산에 따라 행 또는 열의 값을 키로 하고, 그 값의 등장횟수를 밸류로 저장한다.
# 2. 이후 딕셔너리의 items를 하나씩 출력한 뒤, 리스트 형태로 이를 저장한다.
# 3. 리스트 내에서 수의 등장횟수와 수를 통해 오름차순으로 정렬한다.
# 4. 모든 행과 열에 대해 최대 길이만큼 배열의 크기를 맞춘다.
# 5. 이를 모든 행과 열에 대해서 A[r][c]가 k가 될 때까지 반복한다.

r, c, k = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(3)]
# r, c, k = 1, 2, 2
# A = [[1, 2, 1], [2, 1, 3], [3, 3, 3]]

# R 연산: 모든 행에 대해 정렬 수행, 행 개수 >= 열 개수
def R():
    max_count = 0
    for i in range(len(A)):
        count = 0
        dic = {}

        # 1번
        for x in A[i]:
            if x == 0:
                continue
            if x not in dic.keys():
                dic[x] = 0
            dic[x] += 1
        # 2번
        temp = []
        for num, freq in dic.items():
            temp.append([num, freq])
        # 3번
        temp.sort(key=lambda x: (x[1], x[0]))
        if len(temp) >= 50:
            temp = temp[:50]
        A[i] = []
        for j in range(len(temp)):
            for k in range(2):
                A[i].append(temp[j][k])
                count += 1
        max_count = max(max_count, count)

    for i in range(len(A)):
        while len(A[i]) < max_count:
            A[i].append(0)

def C():
    max_count = 0
    for i in range(len(A[0])):
        count = 0
        dic = {}
        
        # 1번
        for j in range(len(A)):
            x = A[j][i]
            A[j][i] = 0
            if x == 0:
                continue
            if x not in dic.keys():
                dic[x] = 0
            dic[x] += 1

        # 2번
        temp = []
        for num, freq in dic.items():
            temp.append([num, freq])

        # 3번
        temp.sort(key=lambda x: (x[1], x[0]))
        if len(temp) >= 50:
            temp = temp[:50]

        while len(temp) * 2 > len(A):
            A.append([0 for _ in range(len(A[0]))])
        
        j = 0
        for x1, x2 in temp:
            A[j][i] = x1
            A[j+1][i] = x2
            count += 2
            j += 2
        max_count = max(max_count, count)

result = 0
while (len(A) < r or len(A[0]) < c) or A[r-1][c-1] != k:
    if result > 100:
        break
    if len(A) >= len(A[0]):
        R()
    else:
        C()
    # print(A)
    result += 1

if result > 100:
    print(-1)
else:
    print(result)