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

30 Dec 2022 in Study on Algorithm

백준18111 마인크래프트 링크

문제

예제 입력

---

코드

import sys
n, m, b = map(int, sys.stdin.readline().split())

arr = []
for _ in range(n):
    arr += list(map(int, sys.stdin.readline().split()))

max = max(arr)
min = min(arr)
minTime = float('inf') # n * m * 256 * 2
Top = 0

for i in range(min, max+1):
    time = 0
    chance = b
    for j in arr :

        if i > j :
            chance -= (i - j)  
            time += (i - j)
        elif i < j :
            chance += (j - i)
            time += 2 * (j - i)

    if chance >= 0 and time <= minTime:
        minTime = time
        Top = i

print(minTime, Top)

설명

파이썬을 통해서 사용자로부터 입력받아 조건문/반복문을 사용하여 마인크래프트을 구현했습니다. 그런데 계속 시간 초과가 발생해서 문제점을 찾아보았는데 Python3 컴파일러로 했다가 PyPy3컴파일로 바꾸는 해결되었습니다.
원래 알던 개념은 Python3의 실행시 시간이 매우 오래 걸린다는 단점이 있어, PyPy3가 그것을 개선하고자 JIT컴파일 방식을 도입한 것이라고 알고 있었습니다.

컴파일 언어 : 소스 코드를 기계어로 컴파일(Compile time) -> 실행파일 만듦 -> 실행(Run time)

인터프리터 언어 : 코드를 한줄씩 읽어 가며 실행

PyPy3에서는 실행시 자주 쓰이는 코드를 캐싱하는 기능이 있기 때문에, 즉 메모리를 조금 더 사용하여 그것들을 저장하고 있어 실행속도를 개선할 수 있다는 것이기 때문이고
간단한 코드상에서는 Python3가 메모리, 속도 측에서 우세할 수 있는 것이고, 복잡한 코드(반복)을 사용하는 경우에서는 PyPy3가 우세합니다.
-> 코드 상황에 맞추어 두 구현체(PyPy3, Python3)를 적절하게 사용하는 것이 효율적이라고 할 수 있다.

---

정리

import sys
from collections import Counter

n, m, inven = map(int, sys.stdin.readline().split())
ground = []
for _ in range(n): ground += map(int, sys.stdin.readline().split())
height, time = 0, float('inf')
print(ground)

min_h = min(ground)
max_h = max(ground)
_sum = sum(ground)
ground = dict(Counter(ground))

for i in range(min_h, max_h + 1):
    if _sum + inven >= i * n * m:
        cur_time = 0
        for key in ground:
            if key > i:
                cur_time += (key - i) * ground[key] * 2
            elif key < i:
                cur_time += (i - key) * ground[key]
        if cur_time <= time:
            time = cur_time
            height = i

print(time, height)

Python3 컴파일러로 했을 때 Counter 자료형과 블럭 갯수가 조건을 만들어 정상 결과를 출력합니다.

---

결과