Lv.1 바탕화면 정리

코딩테스트 연습 - 바탕화면 정리 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 풀이 : 리턴 값으로 만들어야 할 min/max 값들을 꾸준히 업데이트해주는 코드

def solution(wallpaper):
    min_x, min_y, max_x, max_y = 1e5, 1e5, 0, 0

    for i in range(len(wallpaper)):
        for j in range(len(wallpaper[0])):
            if wallpaper[i][j] == '#':
                min_x = min(min_x, i)
                max_x = max(max_x, i + 1)
                min_y = min(min_y, j)
                max_y = max(max_y, j + 1)

    return [min_x, min_y, max_x, max_y]

 

위의 경우에는 완전 탐색을 통해 업데이트 하는데 반해, 그럴 필요 없이 진행할 수도 있다.

 

def solution(matrix):
    for i,row in enumerate(matrix):
        if "#" in row:
            minx=i
            break
    for i, row in enumerate(matrix[::-1]):
        if "#" in row:
            maxx=len(matrix)-i
            break
    for i, col in enumerate(zip(*matrix)):
        if "#" in col:
            miny=i
            break
    for i, col in enumerate(list(zip(*matrix))[::-1]):
        if "#" in col:
            maxy=len(matrix[0])-i
            break
    return [minx,miny,maxx,maxy]

최소/최대 지점부터 시작해서, 가장 최소/최대인 값을 찾는다면 그 즉시 탐색 종료

그럼 탐색할 것들이 적어지면서 시간복잡도 측면에서 충분히 효율을 볼 수 있다.