[Python] 이차원 배열과 연산

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

---

포인트

• 두자리 이상의 수에 대해서 정렬하는 것을 고려
• 100초까지 확인해야 하므로 101번까지 반복해야 함

Tip

• 내장함수 zip(*arr) 을 사용하여 세로 줄에 대해서 정렬을 연산한다.
• Defaultdic 과 DeepCopy를 사용한다.
• 시간을 줄이기 위해 2차원 배열로 연산을 해보자

 

메모리 (제한: 512 MB)

129132 KB

시간  (제한: 0.5 초)

300 ms

결과

100%

from collections import defaultdict
from copy import deepcopy

def array_sort(dic):
    global max_len
    array = []
    for k, v in dic.items():
        array.append((k, v))
    arr = sorted(array, key=lambda p: p[1])
    new_dic = defaultdict(list)
    for a in arr:
        new_dic[a[1]].append(a[0])
    for d in new_dic.keys():
        new_dic[d].sort()
    s = []
    for k, v in new_dic.items():
        for i in v:
            s += [i, k]
    if len(s) > 100:
        s = s[:100]
    max_len = max(max_len, len(s))
    return s


r, c, k = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(3)]
time = 0
answer = -1
while time != 101:
    try:
        if A[r-1][c-1] == k:
            answer = time
            break
    except:
        pass
    max_len = 0
    num_r = len(A)
    num_c = len(A[0])
    if num_r >= num_c:
        _A = []
        for a in A:
            dic = defaultdict(int)
            for _a in a:
                if _a != 0: dic[_a] += 1
            _A.append(array_sort(dic))
        for a in _A:
            a += [0] * (max_len - len(a))
        A = deepcopy(_A)

    else:
        _A = []
        for a in zip(*A):
            dic = defaultdict(int)
            for _a in a:
                if _a != 0: dic[_a] += 1
            _A.append(array_sort(dic))
        for a in _A:
            a += [0] * (max_len - len(a))
        rotate_A = []
        for a in zip(*_A):
            rotate_A.append(list(a))
        A = deepcopy(rotate_A)
    time += 1

print(answer)

 

문제를 푸는데 도움이 된 테스트 케이스

# Input 1 1 1 11 12 13 11 12 11 11 11 11 # Output 3