프로그래머스 바탕화면 정리 JAVA 풀이｜최소 드래그 영역 구하기

🔗 문제 링크

프로그래머스

---

📌 문제 개요

문자열 배열 wallpaper에는 컴퓨터 바탕화면의 상태가 담겨 있습니다.

• .: 빈칸
• #: 파일이 있는 칸

바탕화면에 존재하는 모든 파일을 한 번의 드래그로 선택해야 합니다.

드래그의 시작점은 왼쪽 위 좌표 (lux, luy), 끝점은 오른쪽 아래 좌표 (rdx, rdy)이며 다음과 같은 배열을 반환해야 합니다.

[lux, luy, rdx, rdy]

모든 파일을 포함하면서 드래그 이동거리가 가장 짧은 직사각형의 좌표를 구하는 문제입니다.

---

📌 접근 방법

모든 파일을 포함하는 가장 작은 직사각형을 찾으면 됩니다.

이를 위해 파일이 있는 모든 위치를 확인하면서 다음 네 가지 값을 구합니다.

lux = 파일이 존재하는 가장 위쪽 행
luy = 파일이 존재하는 가장 왼쪽 열
rdx = 파일이 존재하는 가장 아래쪽 행 + 1
rdy = 파일이 존재하는 가장 오른쪽 열 + 1

예를 들어 파일이 (2, 3) 위치의 칸에 있다면 이 파일 전체를 포함하기 위한 오른쪽 아래 격자점은 (3, 4)가 됩니다.

따라서 드래그 끝점에는 행과 열에 각각 1을 더해야 합니다.

---

📌 핵심 아이디어

1. 시작점의 최솟값 구하기

드래그 시작점은 모든 파일보다 위쪽이면서 왼쪽에 있어야 합니다.

lux = Math.min(lux, i);
luy = Math.min(luy, j);

lux에는 파일이 존재하는 행 중 가장 작은 값이 저장됩니다.

luy에는 파일이 존재하는 열 중 가장 작은 값이 저장됩니다.

---

2. 끝점의 최댓값 구하기

드래그 끝점은 모든 파일보다 아래쪽이면서 오른쪽에 있어야 합니다.

rdx = Math.max(rdx, i + 1);
rdy = Math.max(rdy, j + 1);

파일은 격자 칸에 있고 드래그 끝점은 격자점이므로 i와 j에 각각 1을 더합니다.

---

3. 초깃값 설정하기

최솟값을 구하는 변수는 충분히 큰 값으로 시작합니다.

int lux = wallpaper.length;
int luy = wallpaper[0].length();

최댓값을 구하는 변수는 가장 작은 값인 0으로 시작합니다.

int rdx = 0;
int rdy = 0;

파일을 발견할 때마다 Math.min()과 Math.max()를 이용해 좌표 범위를 갱신합니다.

---

📌 전체 코드

class Solution {
    public int[] solution(String[] wallpaper) {
        int lux = wallpaper.length;
        int luy = wallpaper[0].length();
        int rdx = 0;
        int rdy = 0;

        for (int i = 0; i < wallpaper.length; i++) {
            for (int j = 0; j < wallpaper[i].length(); j++) {
                if (wallpaper[i].charAt(j) == '#') {
                    lux = Math.min(lux, i);
                    luy = Math.min(luy, j);
                    rdx = Math.max(rdx, i + 1);
                    rdy = Math.max(rdy, j + 1);
                }
            }
        }

        return new int[]{lux, luy, rdx, rdy};
    }
}

---

📄 정리

• 이차원 문자열 배열을 순회하며 #의 위치를 찾는다.
• 파일이 존재하는 행과 열의 최솟값으로 드래그 시작점을 구한다.
• 파일이 존재하는 행과 열의 최댓값에 1을 더해 드래그 끝점을 구한다.
• Math.min()과 Math.max()를 사용하면 최소 직사각형 영역을 간단하게 계산할 수 있다.
• 시간 복잡도는 바탕화면의 세로 길이를 N, 가로 길이를 M이라고 할 때 O(N × M)이다.
• 격자 칸과 격자점의 차이를 이해하고 끝점에 1을 더하는 것이 핵심이다.