[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을 작성해 보았습니다.