[Python] 마인크래프트 - 백준

해당 글은 백준 18111번 '마인크래프트' 문제를 다룬다.

문제

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

18111번: 마인크래프트

 

설명

해당 문제는 간단한 구현 문제인데, 시간초과를 해결하는데 애를 먹었다.

구현 알고리즘은 배열에 저장된 높이들 중 최소와 최대를 구하여, 해당 높이 범위로 for문을 돌려 각 높이일 때의 걸린 시간을 구하는 것이다. 이때 구한 시간들 중 가장 최소 시간을 정답으로 저장하면 된다.

이때, 처음으로 배열의 행과 열의 인덱스로 접근하는 방법을 사용했는데

Python3으로 제출하면 시간초과가 뜨고, PyPy3으로 제출했을땐 통과되었다.

Python3으로 제출하여 통과할 수 있는 방법을 생각해보다가 Counter 함수를 사용하여 해결하였다.

Counter 함수를 사용한 코드에서 달라진 점은 크게 time와 블록갯수를 추가하거나 뺄 때, 각 높이를 가진 갯수인 v를 곱해주어야 한다.

 

참고) 해당 코드에서 가독성을 위해 elif h_diff < 0:을 사용하였는데

h_diff가 0일 때, abs(h_diff)가 0 이므로 time과 h_b의 변화가 없으므로 else로 구현해도 된다.

 

코드

- PyPy3

import sys
input = sys.stdin.readline

n, m, b = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

min_h, max_h = min(map(min, arr)), max(map(max, arr))
result = [int(1e9), 0]
for h in range(max_h, min_h-1, -1):
    time = 0
    h_b = b
    for i in range(n):
        for j in range(m):
            h_diff = arr[i][j] - h
            if h_diff > 0:
                time += (2*h_diff)
                h_b += h_diff
            elif h_diff < 0:
                time += abs(h_diff)
                h_b -= abs(h_diff)
    if h_b >= 0 and time < result[0]:
        result = [time, h]
print(*result)

     

 

- Python3

from collections import Counter
import sys
input = sys.stdin.readline

n, m, b = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
one_dim_arr = [j for i in arr for j in i]
counter = Counter(one_dim_arr)

min_h, max_h = min(counter), max(counter)
result = [int(1e9), 0]
for h in range(max_h, min_h-1, -1):
    time = 0
    h_b = b
    for k, v in counter.items():
        h_diff = k - h
        if h_diff > 0:
            time += (2*h_diff)*v
            h_b += h_diff*v
        elif h_diff < 0:
            time += abs(h_diff)*v
            h_b -= abs(h_diff)*v
    if h_b >= 0 and time < result[0]:
        result = [time, h]
print(*result)