바탕화면 정리(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

 

 

문제 접근 방식

바탕화면의 모든 파일을 최소한의 크기로 한 번에 선택해야하는 문제이며, 이를 위해서는 상하좌우로 가장 끝 위치를 구해서 드래그하면 된다. 즉, wallpaper를 순회하면서 top, bottom, left, right의 끝 좌표를 구하고 이를 반환한다. 이때 주의할 점은 드래그의 좌표는 격자점이기 때문에 bottom, right 의 좌표는 1 씩 추가해서 반환해야 한다. 

 

 

시간 복잡도

NxM 크기의 이차원 배열인 wallpaper를 순회해야하기 때문에 O(NM)이 걸리며, N과 M의 최댓값이 50이므로 시간 내에 동작한다.

 

 

코드

def solution(wallpaper):
    n=len(wallpaper)
    m=len(wallpaper[0])
    min_l,max_r,min_t,max_b=m-1,0,n-1,0
    for i in range(n):
        for j in range(m):
            if wallpaper[i][j]=='#':
                min_l=min(min_l,j)
                max_r=max(max_r,j)
                min_t=min(min_t,i)
                max_b=max(max_b,i)
    
    answer = [min_t,min_l,max_b+1,max_r+1]
    return answer