본문으로 건너뛰기

17140 - 이차원 배열과 연산

info

풀이 키워드​

스포주의

구현


풀이 코드​

info
  • 메모리: 34228 KB
  • 시간: 68 ms
import sys
from collections import Counter
input = sys.stdin.readline

def calc(matrix): # R연산
    mx = 0
    for i in range(len(matrix)):
        res = sorted(Counter(matrix[i]).most_common(), key=lambda x:(x[1], x[0]))
        tmp = []
        for v, cnt in res:
            if v == 0: continue
            tmp.append(v)
            tmp.append(cnt)
        matrix[i] = tmp
        mx = max(mx, len(tmp))
    
    # zero padding
    for i in range(len(matrix)):
        if len(matrix[i]) < mx:
            matrix[i].extend([0] * (mx-len(matrix[i])))
    
    return matrix

def solution():
    r, c, k = map(int, input().split())
    r, c = r - 1, c - 1
    A = [0] * 3
    for i in range(3):
        A[i] = list(map(int,input().split()))
    
    for t in range(101):
        rlen = len(A)
        clen = len(A[0])
        if r < rlen and c < clen and A[r][c] == k:
            print(t)
            return
        if rlen >= clen: # R연산
            A = calc(A)
        else: # C연산
            A = calc(list(zip(*A)))
            A = list(zip(*A))
            
    print(-1)


if __name__ == '__main__':
    solution()

풀이 해설​

이 문제의 핵심 로직은 R연산(행연산)과 C연산(열연산)이다.

단,​

R연산은 그러러니 하는데 C연산은 그대로 구현하기에 어딘가 난잡하다.

따라서 C연산을 전치행렬의 R연산으로 치환하여 발상하는 것이 풀이의 핵심이다.

if r < rlen and c < clen and A[r][c] == k:
    print(t)
    return
if rlen >= clen: # R연산
    A = calc(A)
else: # C연산
    A = calc(list(zip(*A)))
    A = list(zip(*A))

📌r < rlen과 c < clen 조건을 체크하는 이유​

R, C연산을 수행하면서 A의 크기가 변동되고
이 과정에서 r과 c가 invalid한 index가 될 수도 있기 때문이다. (이 경우 결과는 -1)

📌전치행렬 만들기​

파이썬에선 zip을 이용하여 쉽게 행렬을 transpose할 수 있다.
list 간 element-wise 하게 묶어주기 때문에 *(unpacking operator)를 이용한 트릭이 가능하다.

a = [[1,2,3], [4,5,6], [7,8,9]]
print(*a)
print(list(zip(*a)))
결과
[1, 2, 3] [4, 5, 6] [7, 8, 9]
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

📌깔삼하게 연산하기​

Counter와 lambda 함수를 통해 one-line으로 퉁칠 수 있다.

def calc(matrix): # R연산
    mx = 0
    for i in range(len(matrix)):
        res = sorted(Counter(matrix[i]).most_common(), key=lambda x:(x[1], x[0]))

Counter 결과를 세부적으로 살펴보자면 다음과 같다.

from collections import Counter
a = [3, 1, 1, 1, 2, 2]
print(Counter(a))
print(Counter(a).most_common())
결과
Counter({1: 3, 2: 2, 3: 1})
[(1, 3), (2, 2), (3, 1)]

caution

WA! 끝내주는 낚시!​

문제의 첫 문장을 읽어보자.

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

그러하다.

  1. 인덱스를 1부터 시작한다고 가정하므로 실제 인덱스 접근은 r-1, c-1이 된다.

  2. '1초가 지날때마다' 이므로 반복문을 100까지 순회해야 한다. 반복 자체가 100번 돌아가는것과 무관하다. 0~1로 올라갈때의 연산은 1초가 지날 때의 연산, 99~100으로 올라갈때의 연산은 100초가 지날 때의 연산이 된다.


메모​

  • 유익해요...