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

문제

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

프로그래머스

 

풀이

격자 형태로 구성된 바탕화면에서 저장된 모든 파일을 한번에 삭제하기 위해서 왼쪽 상단 드래그 시작점과 오른쪽 하단 드래그 끝점을 구하여야 합니다. 이때 왼쪽 상단 드래그의 시작점의 행,열은 저장된 파일들의 위치들 중에서 최소가 되어야 합니다. 반대로 오른쪽 하단 드래그의 끝점의 행,열은 저장된 파이들의 위치들 중에서 최대가 되어야 합니다.

 

예를 들어 다음과 같은 바탕화면이 있다고 가정합니다. 이때 파일들을 드래그 해서 한번에 삭제하기 위한 왼쪽 상단 드래그의 시작점은 (1,3)이 되고 오른쪽 하단 드래그의 끝점은 (5,8)이 될것입니다.

 

이때 왼쪽 상단 드래그의 시작점인 (1,3)은 파일들의 위치들중에서 최소 행, 최소 열의 값을 가지는 것을 알 수 있습니다. 반대로 오른 쪽 하단 드래그의 끝점인 (5,8)은 파일들의 위치들 중에서 최대 행, 최대 열의 값을 가지는 것을 알 수 있습니다.

 

왼쪽 상단 드래그 시작점의 최솟값과 오른쪽 하단 드래그 끝점의 최댓값을 구하기 위해서 다음과 같이 수행합니다.

1. 2차원 배열을 순회하며 "#"을 탐색합니다.

2. 만약 그 위치가 "#"이라면 해당 행, 열(i, j)을 왼쪽 상단 드래그 시작점(lux, luy)와 비교하여 최솟값을 왼쪽 상단 드래그의 시작점으로 저장합니다. 그리고 행, 열은 오른쪽 하단 드래그 끝점(rux, ruy)와 비교하여 최댓값을 오른쪽 하단 드래그의 끝점으로 저장합니다.

3. 모든 "#"을 탐색할때까지 1~2번 과정을 반복합니다.

4. 결과배열에 lux, luy, rux + 1, ruy + 1의 값을 넣어 반환합니다. rux와 ruy에 +1을 하는 이유는 "#"을 탐색한 행, 열의 위치가 "#"을 기준으로 왼쪽 상단의 위치이기 때문에 파일들을 드래그하여 범위에 넣기 위해서는 +1을 해주어야 합니다. 예를 들어 위 예제에서 3번 과정을 마쳤을때 rux, ruy는 (4,7)이 됩니다. 파일들을 드래그하여 범위에 넣기 위해서는 오른쪽 드래그의 끝점은 (5,8)이 되어야 합니다.

 

위 예제에 대한 디버깅 표는 다음과 같습니다.

 

코드

class Solution {
    public int[] solution(String[] wallpaper) {
        int lux = wallpaper.length;
        int luy = wallpaper[0].length();
        int rux = 0;
        int ruy = 0;
        
        String[][] map = new String[wallpaper.length][];
        for(int i = 0; i < wallpaper.length; i++){
            map[i] = wallpaper[i].split("");
        }
        
        for(int i = 0; i < wallpaper.length; i++){
            for(int j = 0; j < wallpaper[i].length(); j++){
                if(map[i][j].equals("#")){
                    lux = Math.min(lux, i);
                    luy = Math.min(luy, j);
                    rux = Math.max(rux, i);
                    ruy = Math.max(ruy, j);
                }
            }
        }
        return new int[]{lux, luy, rux + 1, ruy + 1};
    }
}

 

References

https://mydevlogg.tistory.com/21