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

문제

 

접근 방법

1. 바탕화면에서 모든 파일의 좌표를 구합니다.

2. 파일의 좌표들 중 최소 x, y 값과 최대 x, y 값을 구하여 반환합니다.

 

풀이 과정

문제를 살펴보면, 바탕화면을 드래그하여 모든 파일을 선택할 수 있어야 하며, 그러한 드래그 범위 중에 최소값을 리턴해야 합니다. 곰곰이 생각해봅시다. 드래그 범위 중에 최소값은 어떻게 판단할 수 있을까?

 

여기서 최소값 이라는 단어 보다는 모든 파일을 선택할 수 있어야 한다에 한번 집중해보겠습니다. 모든 파일을 커버하려면 여러 파일들의 좌표 중 x 값이 가장 작은 것, y 값이 가장 작은 것을 찾고 해당 좌표 (x1,y1) 부터 여러 파일들의 좌표 중 x 와 y 의 값이 가장 큰 것을 찾아 (x2, y2) 로 두고 두 좌표의 거리를 구하면 됩니다.

 

그럼 이제 문제에서 주어진 조건을 살펴봅시다. 바탕화면의 상태를 나타내는 wallpaper 는 각 원소의 길이가 동일한 문자열 배열입니다. 예를 들어, wallpaper[0] 의 값은 ".#..."이고, 파일이 두 번째 인덱스에 위치한(#) 길이 5의 문자열인 것입니다. 그렇다면 wallpaper[1], wallpaper[2] 의 값의 문자열 길이 또한 5라는 것입니다.

 

이를 이용해서 wallpaper 배열을 우리가 좌표를 구하기 쉬운 int형의 2차원 배열 격자판으로 변환해줍시다.

//격자판 만들기
int[][] board = new int[wallpaper.length][wallpaper[0].length()];

 

만들어진 board 는 각 원소의 값이 모두 0으로 초기화되어 있습니다. int 자료형의 기본값은 0이기 때문이죠. 이제 여기서 우리는 파일의 위치를 찾아 표시를 해주어야 합니다. 저는 파일이 위치한 곳을 board 에서 1로 표시하기로 했습니다.

//파일이 위치한 곳 찾기
for(int i = 0; i < wallpaper.length; i++) {
    for(int j = 0; j < wallpaper[i].length(); j++) {
        if(wallpaper[i].charAt(j) == '#') {
            board[i][j] = 1;
        }
    }
}

 

파일이 위치한 곳에는 이제 1이 찍혔을 거고, 나머지 원소는 모두 0인 상태로 있을 것입니다. 이제 이 격자판을 for 문을 돌면서 파일의 위치를 찾고, 해당 위치의 좌표를 저장해줍시다. 그래야 나중에 파일들의 좌표 중에서 (x, y) 의 최소값과 최대값을 찾을 수 있겠죠.

//격자판에서 파일들의 좌표 구하기
List<int[]> pos = new ArrayList<>();
for(int i = 0; i < board.length; i++) {
    for(int j = 0; j < board[i].length; j++) {
        if(board[i][j] == 1) {
            pos.add(new int[]{i, j});
        }
    }
}

 

파일들의 좌표를 저장할 pos 를 초기화 해줍니다. pos 에는 파일들의 좌표를 찾는대로 순서대로 삽입할 것이기 때문에 List 자료구조를 사용했습니다. 그리고 List 의 각 요소에는 (x, y) 의 좌표가 들어가야 하므로 int 형 1차원 배열로 선언해줍니다.

 

격자판을 이중 for 문으로 돌면서 파일이 위치한 곳을 찾습니다. 우리는 격자판에서 파일의 위치에 1을 표시해두었으니, board[i][j] 의 원소값이 1인 경우 해당 위치를 pos에 차례대로 저장해주기만 하면됩니다.

 

이제 pos 에는 파일이 위치한 좌표들로 가득찼을 겁니다. 남은 일은 간단합니다. 파일들의 좌표 중에서 x, y 의 최소값과 최대값을 구하기만 하면 됩니다.

//파일들의 좌표 중 x,y 의 최소값과 최대값 구하기
int lux = Integer.MAX_VALUE;
int luy = Integer.MAX_VALUE;
int rdx = Integer.MIN_VALUE;
int rdy = Integer.MIN_VALUE;
for(int i = 0; i < pos.size(); i++) {
    lux = Math.min(lux, pos.get(i)[0]);
    luy = Math.min(luy, pos.get(i)[1]);
    rdx = Math.max(rdx, pos.get(i)[0]);
    rdy = Math.max(rdy, pos.get(i)[1]);
}

 

pos 를 for 문으로 돌면서, lux 에는 최소 x 값을 넣습니다. 여기서 주의할 점은 x 의 값이 세로좌표, y 의 값이 가로좌표라는 점입니다. 우리가  흔히 알고있는 x, y 축을 반대로 생각해야 int 형 2차원 배열과 매칭이 됩니다. 그래서 x, y의 좌표를 int[y][x] 로 표시하는 경우도 있지만, 저는 이게 오히려 헷갈려서 x 를 세로좌표, y 를 가로좌표로 두고 int[x][y] 로 표시합니다. 물론 이건 정답이 있는게 아니라 본인만의 스타일대로 진행하시면 됩니다!

 

처음에 pos 에 값을 넣을 때 x 좌표인 i, y 좌표인 j 를 넣었으니 우리는 여기서 pos.get(i)[0] 이 x 좌표, pos.get(i)[1] 이 y 좌표인 것을 알고있습니다. 이를 각 변수 lux, luy, rdx, rdy 값과 비교하며 최소값 및 최대값을 구하여 대입해주면 됩니다.

 

위의 for 문이 끝나고나면, 이제 lux, luy, rdx, rdy 값에 차례대로 우리가 원하는 최소 x, 최소 y, 최대 x, 최대 y 값이 들어가있을 겁니다.

 

이제 문제의 요구대로 시작점 (lux, luy), 끝점 (rdx, rdy) 을 차례대로 담은 정수 배열로 리턴해주면 됩니다. 다만 여기서도 한 가지 주의 사항이 있습니다!

 

(lux, luy) 의 값은 최소값이므로 그대로 반환해주면 되지만, (rdx, rdy) 는 각 값에 1을 더해서 리턴해주어야 합니다. 그 이유는 바탕화면을 마우스로 드래그했을 때 (rdx, rdy) 좌표 중 어느 하나라도 해당하는 좌표에 위치한 파일까지 선택이 되려면, (rdx+1, rdy+1) 좌표를 끝점으로 드래그해야 이 파일들까지 커버가 되기 때문입니다. (사실 이건 처음 코드 실행할 때 돌려보고 실패한 결과를 보고 눈치챘습니다..하하)

 

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

 

제출 결과

 

모든 테스트 케이스가 통과하며 문제가 정답처리 되었습니다!

 

전체 코드

import java.util.*;
class Solution {
    public int[] solution(String[] wallpaper) {
        int[] answer = {};
        
        //격자판 만들기
        int[][] board = new int[wallpaper.length][wallpaper[0].length()];
        
        //파일이 위치한 곳 찾기
        for(int i = 0; i < wallpaper.length; i++) {
            for(int j = 0; j < wallpaper[i].length(); j++) {
                if(wallpaper[i].charAt(j) == '#') {
                    board[i][j] = 1;
                }
            }
        }
        
        //격자판에서 파일들의 좌표 구하기
        List<int[]> pos = new ArrayList<>();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                if(board[i][j] == 1) {
                    pos.add(new int[]{i, j});
                }
            }
        }
        
        //파일들의 좌표 중 x,y 의 최소값과 최대값 구하기
        int lux = Integer.MAX_VALUE;
        int luy = Integer.MAX_VALUE;
        int rdx = Integer.MIN_VALUE;
        int rdy = Integer.MIN_VALUE;
        for(int i = 0; i < pos.size(); i++) {
            lux = Math.min(lux, pos.get(i)[0]);
            luy = Math.min(luy, pos.get(i)[1]);
            rdx = Math.max(rdx, pos.get(i)[0]);
            rdy = Math.max(rdy, pos.get(i)[1]);
        }
            
        return new int[]{lux, luy, rdx+1, rdy+1};
    }
}

 

마치며

최근 한 군데 코딩테스트를 본 적이 있는데, 3년차 임에도 불구하고 제 알고리즘 실력이 처참하다는 것을 깨달아버렸습니다. 그래서 일주일 전부터 알고리즘 공부를 하고 있는데, 이 바탕화면 정리 문제는 제가 작년에 한번 훑어봤다가 포기해버린 문제입니다. 레벨 1 인데도 말이죠..

 

그래서 이제 일주일정도 알고리즘 공부를 했고, 앞으로도 계속 할거니 프로그래머스의 문제를 하나씩 풀어보자. 가급적이면 예전에 도전했다가 실패했던 문제들부터 풀어보자 라는 생각으로 하나씩 풀어보고 있습니다.

 

다행히 레벨 1이지만 문제들이 풀리고 있습니다 ㅎㅎ

 

제 목표는 프로그래머스 레벨2의 문제들을 깔끔하게 해결하고, 문제3은 좀 쩔쩔메다가(?) 풀 수 있는 실력까지 알고리즘을 공부하는 것입니다.

 

spring, jpa 등의 기술들을 깊이있게 공부하고있지만, 알고리즘은 따로 공부하지 않는 이상 아무리 연차가 쌓인다고 해도 제자리 걸음일 수 있다는 위기감을 느꼈기에 알고리즘 공부는 하루에 1문제 씩이라도 꾸준히 할 예정입니다.

 

긴 포스트 읽어주셔서 감사합니다!