마인크래프트

문제

나의 풀이 (TLE)

import sys

for test_case in range(1):
    n, m, b = map(int, sys.stdin.readline().split())
    graph = []

    for _ in range(n):
        graph.append(list(map(int, sys.stdin.readline().split())))

    ans = []
    for earthHeight in range(256, -1, -1):
        inventory = b
        needs = 0
        time = 0
        for row in range(n):
            for col in range(m):
                if graph[row][col] >= earthHeight:
                    inventory += graph[row][col]-earthHeight
                    time += 2*(graph[row][col]-earthHeight)
                else:
                    needs += earthHeight - graph[row][col]
                    time += earthHeight - graph[row][col]

        if inventory >= needs:
            ans.append([time, earthHeight])

    ans.sort(key=lambda x:(x[0], -x[1]))

    print(' '.join(map(str,ans[0])))

브루트 포스로 구현하였다.
땅의 높이는 256블록까지라고 명시를 했으므로 earthHeight를 땅의 높이를 0 ~ 256까지 나타내는 변수로 지정하였다.
만약 earthHeight보다 현재 땅이 높다면 그 차이 만큼 inventory에 넣을 수 있다. 넣을 때 시간은 2초가 걸리므로 2*(현재땅 - eathHeight)를 해준다.
반면에 earthHeight가 현재 땅보다 낮다면 필요한 땅을 저장하는 변수인 needs 변수에 추가해준다. 이 때 time은 1초가 걸리므로 그 차이만큼 더해준다.
만약 inventory에 저장된 땅보다 필요한 땅 갯수가 많다면 고르게 할 수 있다는 의미이므로 ans리스트에 넣어준다.

하지만 3중 for문이라 그런지 TLE가 발생하였다.

나의 풀이 (pass)

import sys

def solution():
    for test_case in range(1):
        n, m, b = map(int, sys.stdin.readline().split())
        graph = []
        start = 0
        end = int(6.4 * 10**7)
    
        for _ in range(n):
            graph.append(list(map(int, sys.stdin.readline().split())))
    
        ans = []
        for earthHeight in range(256, -1, -1):
            inventory = b
            needs = 0
            time = 0
            for row in range(n):
                for col in range(m):
                    if graph[row][col] >= earthHeight:
                        inventory += graph[row][col]-earthHeight
                        time += 2*(graph[row][col]-earthHeight)
                    else:
                        needs += earthHeight - graph[row][col]
                        time += earthHeight - graph[row][col]
    
            if inventory >= needs:
                ans.append([time, earthHeight])
    
        ans.sort(key=lambda x:(x[0], -x[1]))
    
        print(' '.join(map(str,ans[0])))

solution()

이상하게 function코드와 global코드 간에 속도 차이가 있었다.
TLE가 발생한 코드를 function안에다가 작성하면 통과가 되는 것이였다.
그 이유는 자세히 이해하지는 못했지만
python의 경우 전역 변수와 지역 변수는 접근 시간이 다릅니다. 함수 선언을 하지 않을 경우 변수는 전역 변수가 되어 느린 접근 속도를 보이고, 함수 내부에서 정의한 변수는 지역 변수가 되어 빠른 접근 속도를 보입니다.
라는 것이다.

개선 (3중 for문에서 2중 for문으로)

import sys

for test_case in range(1):
    n, m, b = map(int, sys.stdin.readline().split())
    graph = []
    dp = {}

    for _ in range(n):
        tmp = list(map(int, sys.stdin.readline().split()))
        for num in tmp:
            if num not in dp:
                dp[num] = 1
            else:
                dp[num] += 1


    ans = []
    for earthHeight in range(257):
        inventory = b
        needs = 0
        time = 0

        for height in list(dp.keys()):
            cnt = dp[height]
            if height >= earthHeight:
                inventory += (height - earthHeight)*cnt
                time += 2*(height - earthHeight)*cnt
            else:
                needs += (earthHeight - height)*cnt
                time += (earthHeight - height)*cnt
        if inventory >= needs:
            ans.append([time, earthHeight])

    ans.sort(key=lambda x:(x[0], -x[1]))

    print(' '.join(map(str,ans[0])))

3중 for문이 나오는 이유는 최소 높이를 찾고자 하는 for문과 입력받은 graph(2중 list)를 순회하기 위해서 사용하는 2중 for문 때문에 TLE가 발생하였다.

하지만 2중 for문으로 바꿀 수 있다. dictionary를 이용하는 것이다.
예를 들어
64 63 62 60
64 64 64 64
63 63 62 60
이 입력으로 주어줬다고 가정해보자
2중 for문으로 모든 배열을 순회하면 12가 걸린다.

반면에 dictionary에
{
64 : 5,
63 : 3,
62 : 2,
60 : 2
} 라면 4번만 순회하고 해당 횟수를 통해 시간을 구하면 되는 것이다.
이렇게 해서 2중 for문으로 하면 빠르게 통과될 수 있다.