[99클럽 코테 스터디] 26일차 TIL 시뮬레이션

 

 

오늘의 문제는 프로그래머스

 

바탕화면 정리

 

 

문제

 

 

문제 설명 

바탕화면의 파일을 삭제해 정리하려고 합니다. 바탕화면은 정사각형의 격자판이고 바탕화면의 상태를 나타내는 문자열 wallpaper가 주어집니다. 가장 왼쪽 위 (0, 0) 부터 시작해서 파일이 있는 칸은 "#", 파일이 없는 칸은 "." 이라고 했을 때 드래그로 파일을 선택해 한 번에 지워야 합니다. 

드래그는 격자점 S(lux, luy)를 마우스 왼쪽 버튼으로 클랙한 상태로 격자점 E(rdx, rdy)로 이동한 다음 마우스 왼쪽 버튼을 떼는 것을 말합니다. 

S를 시작점, E를 끝점이라고 할 때 드래그의 한 거리 |rdx - lux| + |rdy - luy| 값이 최솟값일 때의 정수 배열 [lux, luy, rdx, rdy]를 반환하는 문제입니다. 

 

입력 값이 wallpaper = [".#...", "..#..", "...#."] 일 때 반환 값은 [0, 1, 3, 4] 입니다. 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 51분이 걸렸습니다.

 

 

 

 

문제 접근 방식

먼저 wallpaper가 1차원 배열로 주어졌기 때문에 이를 2차원 배열로 변환하여 격자판을 생성합니다. 이중 for문을 사용해 2차원 배열의 요소를 순회하고 값이 #인 경우 해당 위치의 행과 열을 각각 ArrayList에 저장합니다. 반복문이 끝나면, 저장된 ArrayList 를 오름차순으로 정렬하고 첫 번째 요소와 마지막 요소를 변수에 저장하여 결과로 반환합니다. 

 

 

 

문제 풀이

import java.util.Arrays;
import java.util.ArrayList; 
import java.util.Comparator;

class Solution {
    public int[] solution(String[] wallpaper) {
        
        int row = wallpaper.length;
        int col = wallpaper[0].length();
        
        String[][] wallPaper = new String[row][col];
        
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                wallPaper[i][j] = String.valueOf(wallpaper[i].charAt(j));
            }
        }
        
        ArrayList<Integer> rows = new ArrayList<Integer>();
        ArrayList<Integer> cols = new ArrayList<Integer>();
        
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(wallPaper[i][j].equals("#")) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        
        rows.sort(Comparator.naturalOrder());
        cols.sort(Comparator.naturalOrder());

        int lux = rows.get(0);
        int rdx = rows.get(rows.size() - 1)  + 1;
        int luy = cols.get(0);
        int rdy = cols.get(cols.size() - 1) + 1;
        
        int[] answer = {lux, luy, rdx, rdy};
        
        return answer;
    }
}

 

 

rdx와 rdy의 값을 1 증가시키는 이유

마지막 값에 1을 더하는 이유는, # 문자가 위치한 마지막 행과 열을 나타내는 값은 해당 문자가 포함된 행과 열의 시작점을 나타내기 때문입니다. 하지만 사각형의 범위를 정확하게 정의하려면 그 끝점을 포함해야 합니다. 따라서 rdx와 rdy에 1을 더해줌으로써, 해당 문자가 포함된 마지막 행과 열의 끝점까지 포함하여 사각형의 범위를 정확하게 나타낼 수 있습니다.

 

 

 

 

코드 개선하기

기존 코드에서 사용하던 이차원 배열을 제거하고 String[] wallpaper 배열에서 바로 charAt 메서드를 사용해 문자를 비교하는 방식으로 수정했습니다. 

import java.util.ArrayList; 
import java.util.Comparator;

class Solution {
    public int[] solution(String[] wallpaper) {
        
        int row = wallpaper.length;
        int col = wallpaper[0].length();
        
        ArrayList<Integer> rows = new ArrayList<>();
        ArrayList<Integer> cols = new ArrayList<>();
        
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(wallpaper[i].charAt(j) == '#') {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        
        rows.sort(Comparator.naturalOrder());
        cols.sort(Comparator.naturalOrder());

        int lux = rows.get(0);
        int rdx = rows.get(rows.size() - 1) + 1;
        int luy = cols.get(0);
        int rdy = cols.get(cols.size() - 1) + 1;
        
        return new int[]{lux, luy, rdx, rdy};
    }
}

 

 

 

 

다른 풀이 

아래 코드는 wallpaper 배열에서 # 문자가 포함된 사각형의 경계를 나타내는 좌표를 계산합니다. 

이중 for문을 사용해 wallpaper의 모든 요소를 순회합니다. wallpaper[i].charAt(j) == '#' 조건을 통해 # 문자가 있는 위치를 확인합니다. 각 #의 좌표를 추적해 현재까지 발견된 최소 및 최대 좌표와 비교합니다. 

최종적으로 minX와 minY는 사각형의 가장 왼쪽 위를 나타내고, maxX와 maxY는 가장 오른쪽 아래를 나타냅니다. 

class Solution {
    public int[] solution(String[] wallpaper) {
        
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;
        int maxY = Integer.MIN_VALUE;
        
        for(int i=0; i< wallpaper.length;i++ ){
            for(int j=0; j<wallpaper[i].length();j++){
                if(wallpaper[i].charAt(j)=='#'){
                    minX = Math.min(minX,i);
                    minY = Math.min(minY,j);
                    maxX = Math.max(maxX,i);
                    maxY = Math.max(maxY,j);
                }
            }
        }
        
        return new int[]{minX,minY,maxX+1,maxY+1};
    }
}

 

 

 

 

 

 

 

 

 

 

이렇게 오늘 26일차 TIL을 작성해 보았습니다.