[프로그래머스/JAVA] 바탕화면 정리

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 🔍 최종 코드
• 💻 실행 흐름 예시
• 💡 핵심 포인트
• 🕑 시간 복잡도

 

 

 

🔗 문제 바로가기

프로그래머스

 

 

📌 문제 요약

1️⃣ 문자열 배열 wallpaper는 컴퓨터 바탕화면을 나타낸다.

2️⃣ "#"은 파일이 있는 칸이고, "."은 빈칸이다.

3️⃣ 한 번의 드래그로 모든 파일을 선택해서 지우고자 한다.

4️⃣ 드래그는 (lux, luy) ~ (rdx, rdy)로 직사각형을 형성하며, 최소한의 영역을 선택히야 한다.

5️⃣ 반환 형식: [lux, luy, rdx, rdy]

 

 

✅ 최종 코드

public class Solution {
    public int[] solution(String[] wallpaper) {
        int[] answer = new int[4];

        int top = -1;
        int bottom = -1;
        int left = -1;
        int right = -1;

        for(int i = 0; i < wallpaper.length; i++) {
            for(int j = 0; j < wallpaper[i].length(); j++) {
                if(wallpaper[i].charAt(j) == '#') {
                    if(top == -1 || top > i) {
                        top = i;
                    }

                    if(left == -1 || left > j) {
                        left = j;
                    }

                    if(right < j) {
                        right = j;
                    }

                    if(bottom < i) {
                        bottom = i;
                    }
                }
            }
        }

        answer[0] = top;
        answer[1] = left;
        answer[2] = bottom + 1;
        answer[3] = right + 1;

        return answer;
    }
}

 

 

 

👩🏻‍💻 실행 흐름 예시

다음과 같은 입력이 들어왔다고 하자.

[".#...", 
 "..#..", 
 "...#."]

 

이를 표로 보면, 다음과 같다.

0행: . # . . .
1행: . . # . .
2행: . . . # .

 

즉, 가장 위쪽 top = 0

가장 아래쪽 bottom = 2

가장 왼쪽 left = 1

가장 오른쪽 right = 3

 

 

그러나 중요한 건 bottom과 right 부분인데,

2번째 그림처럼 이 파일을 포함해야 되기 때문에

bottom과 right에 +1씩 해주어서 우측 하단의 끝점을 선택해주어야 한다.

 

즉, 최종 답은 위에서 구한 [0, 1, 2, 3]이 아니라,

[0, 1, 2 + 1, 3 + 1] 즉, [0, 1, 3, 4]이다.

 

 

💡 핵심 포인트

top, left는 시작점 그대로 반환하면 되지만,

bottom, right는 마지막 파일의 아래 행, 오른쪽 열의 격자점까지 포함해야 하므로 +1을 해줘야 한다.

 

 

🕑 시간 복잡도

행과 열을 전체 탐색하므로 O(N * M)