[프로그래머스] 바탕화면 정리 Python 풀이

---

문제

문제가 매우 길어서 링크로 대체하고 설명을 쓰겠다.

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

바탕화면에 파일이 여러 개 있는데 이를 한 번에 묶을 수 있는 최단 루트를 구해서 좌측상단, 우측하단의 좌표를 구하면 된다.

---

구현

문제를 그대로 따라가면서 시간복잡도를 최소화하려면 구현이 복잡해진다.

좌측 상단에서 거리가 0인 포인트 부터 시작해서 파일을 찾아야 한다. [0,0] [1,0], [0,1] ...... 이렇게 해서 아래와 오른쪽에 동시에 있다면 그 점을 넣고

우측하단에서도 같이 하면 된다.

 

하지만 이 문제는 레벨 1이라 파일 위치가 복잡하지 않기 때문에 모든 파일을 찾아서 모두 x,y좌표가 들어있는 배열에 더해주고 최대, 최솟값을 구해서 리턴하면 된다.

---

코드

def solution(wallpaper):
    answer=[]
    a,b=[],[]
    for i in range(len(wallpaper)):
        for j in range(len(wallpaper[i])):
            if wallpaper[i][j] == "#":
                a.append(i)
                b.append(j)
    return [min(a), min(b), max(a)+1, max(b)+1]

---

다른 풀이

def solution(wallpaper):
    rdx, rdy = 0, 0
    lux, luy = 50, 50
    for i in range(len(wallpaper)):
        for j in range(len(wallpaper[0])):
            if wallpaper[i][j] == '#':
                if j <= lux:
                    lux = j
                if i <= luy:
                    luy = i
                if i+1 >= rdx:
                    rdx = i+1
                if j+1 >= rdy:
                    rdy = j+1


    answer = [luy, lux, rdx, rdy]
    return answer

이 방법은 x,y를 계속 비교하면서 최대, 최소 포인트를 잡는 방법이다.

메모리를 덜 쓰는 방법이라 정리해 보았다.