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

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

17140번: 이차원 배열과 연산

 

단순한 연산 구현 문제. 상대적으로 속도가 느린 Python을 사용하였다.

 

시간제한을 맞추기 위해 몇가지 방법을 사용하였다.

• PyPy3로 제출
• heapq, sys 모듈 사용

<Python 코드>

import sys
import collections
import heapq
 
lines = sys.stdin.readlines()
r, c, k = tuple(map(int, lines[0].split()))
init = [list(map(int, line.split())) for line in lines[1:]]
mat = [[0 for _ in range(100)] for _ in range(100)]
for i in range(3):
    for j in range(3):
        mat[i][j] = init[i][j]
 
re = False
w, h = 3, 3
for i in range(100):
    if mat[r-1][c-1] == k:
        print(i)
        re = True
        break
    if h >= w:
        bw = w
        for i in range(h):
            count = collections.Counter(mat[i])
            l = []
            n = len(count)
            for key in count.keys():
                if key != 0:
                    heapq.heappush(l, (count[key], key))
                else:
                    n -= 1
            cw = min(n * 2, 100)
            w = max(w, cw)
            for j in range(cw//2):
                t = heapq.heappop(l)
                mat[i][j*2] = t[1]
                mat[i][j*2+1] = t[0]
            for j in range(cw, bw, 1):
                mat[i][j] = 0
    else:
        bh = h
        for i in range(w):
            count = collections.Counter([col[i] for col in mat])
            l = [] 
            n = len(count)
            for key in count.keys():
                if key != 0:
                    heapq.heappush(l, (count[key], key))
                else:
                    n -= 1
            ch = min(n * 2, 100)
            h = max(h, ch)
            for j in range(ch//2):
                t = heapq.heappop(l)
                mat[j*2][i] = t[1]
                mat[j*2+1][i] = t[0]
            for j in range(ch, bh, 1):
                mat[j][i] = 0
 
if not re:
    if mat[r-1][c-1] == k:
        print(100)
    else:
        print(-1)

 

<Pypy3 vs Python>

 

서버 상태 등, 다른 요인이 있기는 하지만 PyPy 가 반드시 빠른 것은 아닌 듯하다.

다른 분들의 제출 목록에서도 전반적으로 python코드들이 실행시간이 짧았다.