[프로그래머스] PCCP 기출문제 2번

https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

가장 많은 기름을 뽑을 수 있는 양을 찾는 문제.

 

1. 접근

처음 이 문제를 봤을 때, 지점을 순회하면서 BFS나 DFS를 활용해서 얻을 수 있는 기름의 총량의 최대치를 반환해

지속적으로 answer 값을 갱신하고자 했다.

 

2. 초기 코드

import copy
def checker(land, start, depth, width):
    value = 0
    move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    info = [[d, start] for d in range(depth)]
    
    while info:
        row, col = info.pop()
        
        if land[row][col] == 0:
            continue
        
        value += 1
        land[row][col] -= 1
        
        for ad_row, ad_col in move:
            new_row, new_col = row + ad_row, col + ad_col
            
            if 0 <= new_col < width and 0 <= new_row < depth and land[new_row][new_col]:
                info.append([new_row, new_col])
        
    return value

def solution(land):
    answer = 0
    row, col = len(land), len(land[0])
    
    for i in range(col):
        answer = max(answer, checker(copy.deepcopy(land), i, row, col))
        
    return answer

위 코드는 테스트 코드 / 정확성 검사는 무난하게 통과했지만 효율성 검사에서 모두 실패했다. 

이 코드 구성을 보면서 어떤 부분으로 인해 시간이 오래 걸리는지 생각해본 다음, 결론을 내렸다.

'계속해서 기름을 얻을 수 있는 총량을 구하면 안되겠다'

이 결론을 바탕으로 코드 구성을 아래와 같이 바꾸었다.

DFS / BFS로 연결된 기름 정보를 구한다. 단, 최초 한 번만 구하고 이후로는 다시 계산하지 않는다.

이렇게 되면 특정 지점을 기준으로 얻을 수 있는 기름의 총량을 구하기 어려워진다.

이 문제를 해결하기 위해서 얻을 수 있는 기름 정보량과 함께 어디서부터 어디까지 존재하는지에 대한 정보도 함께 포함했다.

 

3. 수정 코드 - 측정 부분

def solution(land):
    
    oil = []
    row_size, col_size = len(land), len(land[0])
    answer = [0 for _ in range(col_size)]
    
    move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    
    for r in range(row_size):
        for c in range(col_size):
            if land[r][c] == 0:
                continue
            
            value, min_col, max_col = 0, col_size, 0
            start = [[r, c]]
            land[r][c] -= 1
            
            while start:
                row, col = start.pop()

                value += 1
                min_col, max_col = min(col, min_col), max(col, max_col)
                
                for ad_row, ad_col in move:
                    new_row, new_col = row + ad_row, col + ad_col

                    if 0 <= new_col < col_size and 0 <= new_row < row_size and land[new_row][new_col]:
                        start.append([new_row, new_col])
                        land[new_row][new_col] -= 1
                        
            oil.append([value, min_col, max_col])

예제 2번

2번 예제를 보면, 12에 해당하는 기름은 1부터 6까지 존재하므로, 어디서 측정을 해도 12를 반환하기 때문에

해당 정보는 리스트에 [12, 0, 5] 로 추가된다.

 

4. 수정 코드 - 정답 부분 1

answer = 0

for i in range(col_size):
	tmp_answer = 0
    for value, min_col, max_col in oil:
        if min_col <= i <= max_col:
        	tmp_answer += value
    
    answer = max(answer, tmp_answer)

return answer

측정 완료 후, land 의 col 길이와 기름 정보량 만큼 순회하면서 측정 위치가 기름의 범위 내 있다면 value 를 더해주고

answer를 갱신하는 방식으로 구현했다. 하지만 해당 방법은 일부 효율성 검사에서 통과하지 못했다.

효율성 검사 통과를 위해 최악의 케이스를 생각해봤는데,

아마도 최대 사이즈인 500 x 500 사이즈 내 기름이 서로 인접하지 않으면서 존재하는 경우, (총 250,000 / 2 = 125,000)

가로 길이를 순회하며 모든 기름 정보를 순회하면 500 x 125,000 = 6,250,000 회 순회하는 경우인 것으로 추측했다.

따라서, 기준을 가로 길이가 아닌, 기름 정보를 기준으로 min_col - max_col 범위 내 존재하는 인덱스에

value 를 추가하고, 최종적으로 max(answer)를 구하는 방법으로 효율성 검사를 통과했다.

 

5. 수정 코드 - 정답 부분 2

answer = [0 for _ in range(col_size)]

for value, min_col, max_col in oil:        
        for i in range(min_col, max_col + 1):
            answer[i] += value
        
    
    return max(answer)