[백준] No.18111_마인크래프트 01

 

18111번: 마인크래프트

예전에 브루트포스 문제를 연습하려고 찾았다가 건너뛰었던 문제이다.

정답률이 24%에 어떻게 푸는지 방법이 감이 안 잡혀서 건너뛰었었다.

하지만 어림도 없었다. 코딩 스터디를 진행하는데, 누군가 이 문제를 가져왔다.

어쩔 수 없이 풀어야 했다. 지금의 나는 강해졌다 덤벼라.

 

문제 자체는 역시나 쉽다.

땅의 높이가 모두 같아질 때, 가장 빨리 심거나 캐는 시간을 구하는 문제이다. 

실제 마인크래프트를 떠올린다면, 블럭 캐는 것과 심는 것은 익숙할 것이다. 캐는 게 훨씬 오래 걸린다.

이 문제에서도 마찬가지로 캐는 게 2초, 심는 것은 1초가 걸린다.

 

근데 이게... 검사가... 시간 안에 다 되나...?

아무리 브루트포스 문제 카테고리여도 1초에 500 * 500 사이즈를 256 높이를 다 계산한다?

그럼 2차원 배열을 돌고, 높이도 도니까 3중 for문(O(n^3))에 6400만 개인데?

해봐야 알지 우선 시도해보자.

 

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Function ----------
def Minecraft(row: int, col: int, inventory: int, ground: list) -> int:
    return

# ---------- Main ----------
row, col, inventory = map(int, input().split())
ground = [list(map(int, input().split())) for _ in range(row)]

second, height = Minecraft(row, col, inventory, ground)
print(second, height)

기본 틀은 여느 때와 같다. 이번 문제만큼은 readline으로 꼭 입력받자.

시간(second)과 높이(height)를 Minecraft 함수 return 값으로 받는다.

이번에는 처음부터 필요한 인자들을 전부 던져주었다.

 

# ---------- Function ----------
def Minecraft(row, col, inventory, ground):
    answer = []
        
    answer = sorted(answer, key = lambda x: (x[1], -x[0]))
    
    return answer[0][1], answer[0][0]

처음에는 Hash 구조를 이용하여 빠른 연산이 가능한 dictionary를 사용했다.

key는 높이, value는 시간으로 잡아주었다. 왜냐하면 높이는 고유하기 때문이다.

하지만 dictionary를 정렬하는 방법을 몰랐다.

그래서 2차원 배열로 바꾸었고 [x][0]은 높이, [x][1]은 시간이다.

 

이제와서 글을 쓰며 생각하는 부분인데 dictionary도 똑같이 lambda로 정렬이 가능할 것 같다.

dict.items()로 item[0], -item[1] 이런 식으로 작성하면 가능하지 않을까?

python3로 작성할 때 한번 시도해봐야 겠다.

 

# ---------- Function ----------
minHeight = min(map(min, ground))
maxHeight = max(map(max, ground))

# Brute Force
for h in range(minHeight, maxHeight+1):
    lessThanH = 0
    moreThanH = 0

시간을 최대한 줄이기 위해서 최소 높이와 최대 높이를 계산했다.

주어진 조건에서의 최소와 최대 높이는 각각 0와 256이다.

하지만 입력받은 높이 중 최소 높이보다 낮을 필요도 없고, 최대 높이보다 높을 필요도 없다 생각했다.

예를 들어 입력의 최저 높이가 3이라면, 굳이 한 칸씩 더 파서 2로 만들 필요가 없다는 말이다. 

 

그리고 높이 h가 있을 때, 당연히 h보다 낮은 땅이 있을 것이고 높은 땅도 있을 것이다.

h보다 낮은 땅은 lessThanH, 높은 땅은 moreThanH로 변수명을 설정해주었다.

최대한 변수명을 직관적으로 지으려고 노력했다.

 

# ---------- Function ----------
# Count less and more block, each height
for r in range(row):
    for c in range(col):
        if ground[r][c] < h: lessThanH += 1
        if ground[r][c] > h: moreThanH += 1

# Checking inventory
if lessThanH > moreThanH + inventory:
    continue

else:
    answer.append([h, (lessThanH*1) + (moreThanH*2)])

2차원 배열을 돌면서 각 땅의 높이를 확인한다.

높이보다 낮다면 lessThanH에 +1을, 높다면 moreThanH에 +1을 해준다.

같은 조건은 굳이 확인할 필요가 없는 게, 같다면 아무런 작업을 하지 않아도 되기 때문이다.

 

중간에 까먹을 뻔했는데 inventory가 있다는 것을 잊어서는 안 된다.

캐낸 블럭(moreThanH) + inventory가 설치해야 하는 개수(lessThanH)보다 작으면 진행 불가능이다.

따라서 continue로 무시하고, 아닐 경우에 (설치하는 개수 * 1초) + (파낸 개수 * 2초)를 answer에 추가한다.

그리고 answer는 위에서 본 것처럼 정렬을 하고 return을 한다.

 

지금 적으면서 코드를 다시 읽는데 고쳐야 할 부분이 한두ㅔ개가 아니긴 하다.

if ~~ continue로 짤 필요 없이, 반대 조건으로 else 구문을 지울 수도 있었다.

또 *1은 문어체를 그대로 옮기다 보니 발생한 실수이다. *1은 그대로이기 때문에 역시나 지워도 된다.

 

python3과 pypy3에서 모두 시간 초과가 났다.

그래도 pypy3에서는 통과하지 않을까 싶었는데 웬 걸 2%에서 틀렸었다.

크게 3가지 부분에서 시간을 줄이려고 해보았고, 틀린 코드를 수정했다.

 

# Before
answer = []

# After
SECOND = 1e9
HEIGHT = -1

첫째,  answer에 모든 값을 추가하는 방식을 개선했다.

값을 추가한 뒤, 정렬을 하고 그 다음에 return을 해주었다.

 └ 파이썬 내장 함수 sort를 사용하여 최악의 경우에도 O(NlogN)을 보장한다.

그러지 않고, 최단 시간을 넣을 SECOND와 그 높이를 넣을 HEIGHT를 선언해주었다.

for문으로 검사하면서 if문을 사용하여 바로바로 계산하여 넣어준다.

 

# Before
if ground[r][c] < h: lessThanH += 1
if ground[r][c] > h: moreThanH += 1

# After
if ground[r][c] > h: moreThanH += ground[r][c] - h
if ground[r][c] < h: lessThanH += h - ground[r][c]

둘째, 아예 틀린 코드를 수정했다.

주어진 테스트 케이스말고 직접 테스트 케이스를 작성해서 수행해보았다. 그랬더니 이상한 답이 나왔다.

예를 들어서 10 10 3이라는 높이가 주어졌고, 현재 검사하는 높이가 5이라고 가정해보자.

그럼 10은 5만큼 줄어들고, 3은 2만큼 증가한다.

이때 1을 더하거나 빼면 몇 개의 공간이 바뀌는지 세는 것이지, 그 공간에서 블록을 얼마나 바꾸는지는 세지 않는다.

그래서 1이 아니라 높이 차만큼 더해주는 방식으로 코드를 바꿔주었다.

 

# Before
if lessThanH > moreThanH + inventory:
    continue
else:
    answer.append([(lessThanH*1) + (moreThanH*2), h])
answer = sorted(answer, key = lambda x: (x[0], -x[1]))

# After
if moreThanH + inventory >= lessThanH:
    currentSecond = (lessThanH) + (moreThanH*2)
    if currentSecond <= SECOND:
        SECOND = currentSecond
        HEIGHT = h

셋째, 위에서도 언급한 고쳐야할 부분이다.

쓸모 없는 부분을 지우고, answer 배열에서 SECOND, HEIGHT로 바꾼 부분도 손봐주었다.

 

와 또 시간 초과가 났다. 그래도 2%에서 끝나지는 않고 80%까지는 버텨주었다.

문제풀이를 시작하고나서부터 여기까지 대략 30분정도의 시간이 소요되었다.

 

30분정도에 이정도까지 짰고, 더 이상 생각나는 부분이 없었다.

그리고 최근에 코테 준비는 30분에서 1시간을 풀어보고 답이 없으면 답이나 보고 공부해라라는 글을 봤었다.

그래서 인터넷에서 코드를 검색해보았고, 내 코드와 거의 비슷해서 조금 놀라웠다.

근데 오히려 내 코드가 더 시간복잡도가 적을 것 같았다.

그래서 여러 가지를 생각해보고, 크게 다섯 가지로 나누어서 코드 개선점을 생각해보았다.  

 

# 바꾸면서 제출한 경우의 수들

# L28 currentSecond 변수를 지움
# L10, 11 minHeight, maxHeight를 지움
# L22 if, if의 이중 if 구조를 if-else로 바꿈

1. 함수 호출

함수를 호출함에 있어서 시간복잡도가 증가하지 않을까 생각했다.

하지만 찾아보니, 함수를 과도하게 호출하는 정도가 아니라면 유의미한 정도가 아니었다.

처음 한 번 호출해주는 정도는 상관이 없어 Main에서 실행하는 형태로 바꾸지 않고 유지했다.

 

2. minHeight와 maxHeight 변수 사용

가장 의문이 들었던 부분이었다. 최소 높이와 최대 높이를 지정해 준 것이었다.

하지만 다른 모든 사람들의 코드에서는 전부 0부터 256 높이까지 확인해주었다.

굳이...? 그래야 하나? 최소 최대 높이를 지정해줘서 무의미한 부분은 확인할 필요 없는 거 아닌가??

브루트포스라고해도 오히려 0부터 256까지 다 도는 게 비효율적인 것 아닌가??

내 코드에서는 minHeight와 maxHeight 변수를 사용할 때 map 내장 함수를 사용하여 계산했다.

map 함수를 사용할 때, 시간이 오래 걸릴 수도 있으니 0부터 256까지 확인하는 방법으로 바꿔보았다.

 

3. 다중 for문 사용

가장 마음에 걸리는 부분이었다. 하지만 for문을 if문으로 바꿔서는 코드 수행이 불가능했다.

그렇다고 단일 for문으로 한 줄씩 받아들여 Counter로 확인을 하려했지만 코드가...더 복잡해졌다.

우선 다중 for문은 보류하기로 했다.

 

4. 다중 if문 사용

얘는 크게 생각이 없었다. 하지만 다른 사람들의 코드를 보고 나서 생각이 들었다.

전부 if - else 구문을 사용했네? 혹시 if if는 어떤 상황이든 2번 검사하니까 오래 걸리지 않을까? 했다.

그래서 검색해보니 생각보다... 다중 if문의 시간이 오래 걸리는 듯하였다.

높이가 같은 경우에는 검사하지 않아도 되어, 높은 경우 낮은 경우 두 가지를 if문으로 받아 처리했다.

하지만 거꾸로 말하면 높이가 같은 경우에는, 높든 낮든 빼서 더해지는 값이 0이라 상관이 없었다.

그래서 이 부분은 if-else 구문으로 바꿔보았다.

 

5. currentSecond 변수 사용

시간 초과에 영향이 있을까 할 정도로 사소한 부분이지만, 그래도 용의선상에 올랐다.

변수를 사용하지 않고, 직접 계산하는 코드로 바꿔보았다.

 

결국 위의 모든 케이스들을 테스트 해 본 결과, 놀랍게도 다중 if 구문의 문제였다.

마지막 맞았습니다!!는 다중 if말고 나머지 부분들을 다시 추가하여 정상적으로 동작하나 확인한 코드이다.

결국 위의 4가지는 상관이 없고, if-if의 문제가 가장 컸다는 것이다.

 

단순하게 if 조건문을 2번 쓰는 것과 if-else 구문을 한 번 쓰는 것에 차이가 없을 거라 생각했다.

하지만 그것은 시간 초과의 여부를 결정할 정도로 차이가 크게 남을 체감했다.

코드의 가독성과 심미성을 위해서 if-else 구문을 사용하지 않았었다.

하지만 효율성을 위해서 간단하게 if-else로 처리 가능한 부분은 최대한 깔끔하게 처리해야 한다는 것을 느꼈다.

 

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Function ----------
def Minecraft(row, col, inventory, ground):
    SECOND = 1e9
    HEIGHT = -1
    
    minHeight = min(map(min, ground))
    maxHeight = max(map(max, ground))
    
    # Brute Force
    for h in range(minHeight, maxHeight + 1):
        lessThanH = 0
        moreThanH = 0
        
        # Count less and more block, each height
        for r in range(row):
            for c in range(col):
                if ground[r][c] <= h: lessThanH += h - ground[r][c]
                else: moreThanH += ground[r][c] - h
                
        # Checking inventory
        if moreThanH + inventory >= lessThanH:
            
            # Chekcing HEIGHT and SECOND
            if (lessThanH) + (moreThanH*2) <= SECOND:
                SECOND = (lessThanH) + (moreThanH * 2)
                HEIGHT = h
                
    return SECOND, HEIGHT

# ---------- Main ----------
row, col, inventory = map(int, input().split())
ground = [list(map(int, input().split())) for _ in range(row)]

second, height = Minecraft(row, col, inventory, ground)
print(second, height)

최종적으로 완성한 PyPy3에서 AC가 뜨는 코드이다.

하지만 PyPy3가 아니라 Python3로 통과하고 싶다는 마음이 있다.

이 완성 코드를 평소처럼 完 글로 따로 나누지 않은 이유는 Python3으로 도전할 것이기 때문이다.

다중 for문 같은 코드나, Counter 그리고 dictionary 정렬을 이용하면 될 것 같은 느낌이 든다.

정답 코드를 검색했을 때, Python3으로 통과한 사람들도 많았다. 나도 할 수 있다.