바탕화면 정리 드래그 범위 계산 – 두 가지 풀이

오늘은 바탕화면 정리 드래그 범위 계산 두가지 풀이법에 대해 적겠어용

일단 해당문제는 큰 알고리즘 개념이 들어가지 않습니다.

---

문제 설명 요약

• 바탕화면은 문자열 배열로 표현되며, "#"는 파일이 존재하는 위치
• 한 번의 드래그로 모든 파일을 선택할 수 있는 최소 범위를 구해야 함
• 드래그 범위는 [lux, luy, rdx, rdy] 형태로 출력해야 함
• 여기서:
  • (lux, luy) = 드래그 시작점 (최소 행, 최소 열)
  • (rdx, rdy) = 드래그 끝점 다음 칸 (최대 행 + 1, 최대 열 + 1)

---

풀이 1 - re를 사용한 풀이

import re

def solve(wallpaper):
    res = [None, None, None, None]
    file_icon = "#"
    for i, row in enumerate(wallpaper):
        if file_icon in row:
            if res[0] is None:
                res[0] = i
            res[2] = i + 1
            files = [m.start() for m in re.finditer(file_icon, row)]
            if res[1] is None:
                res[1] = files[0]
                res[3] = files[-1] + 1
            else:
                res[1] = min(res[1], files[0])
                res[3] = max(res[3], files[-1] + 1)
    return res

풀이 2 - for문 만을 이용한 풀이

def solve(wallpaper):
    min_row, min_col = float('inf'), float('inf') #가장 큰 수
    max_row, max_col = 0, 0
    file_exist_icon = '#'
    for i, v in enumerate(wallpaper):
        for j, cha in enumerate(v):
            if cha == file_exist_icon:
                min_row = min(min_row, i)
                max_row = max(max_row, i + 1) # 마지막 아이콘을 포함시키는 드래그 범위여야하기때문

                min_col = min(min_col, j)
                max_col = max(max_col, j + 1) # 마지막 아이콘을 포함시키는 드래그 범위여야하기때문

    res = [min_row,min_col,max_row,max_col]
    return res

---

두 문제 모두 O(N*M)으로 시간복잡도는 동일합니다.

하지만 1번 풀이의 경우 조건문이 들어가게 되어 가독성이나 구현이 조금 복잡합니다.

2번의 경우는 좀 더 명확한 코드입니다.

여기서 float('inf')는 양의 무한대를 표현하는것 입니다.

1 ≤ wallpaper의 길이 ≤ 50
1 ≤ wallpaper[i]의 길이 ≤ 50
wallpaper의 모든 원소의 길이는 동일합니다.

문제 조건에 50이 있었기 때문에 50으로 나타내도 무방하긴합니다.

또한 re를 사용하는 방식은 내부적으로 패턴 매칭 과정을 포함하므로, for문보다 약간의 오버헤드가 발생할 수 있습니다.