[프로그래머스] Lv.1 바탕화면 정리 JAVA 풀이

문제 Lv.1 바탕화면 정리 (배열 탐색)

 

 : 컴퓨터 바탕화면은 각 칸이 정사각형인 격자판

   컴퓨터 바탕화면의 상태를 나타낸 문자열 배열 = wallpaper

   빈칸은 = "."

   파일이 있는 칸 = "#"

   최소한의 이동거리를 갖는 한 번의 드래그로 모든 파일을 선택해서 한 번에 지우기

   드래그는 "점 S에서 점 E로 드래그한다"

 

   "드래그 한 거리" = |rdx - lux| + |rdy - luy|

   

   예)

   wallpaper = [".#...", "..#..", "...#."]

   S(0, 1)에서 E(3, 4)로 드래그하면 세 개의 파일이 모두 선택

   드래그 한 거리 = (3 - 0) + (4 - 1) = 6을 최솟값

 

1 ≤ wallpaper[i]의 길이 ≤ 50

• 모든 원소의 길이는 동일
• wallpaper[i][j]는 i + 1행 j + 1열에 해당하는 칸의 상태
• "#" 또는 "."의 값
• 바탕화면에는 적어도 하나의 파일이 있다

 

[과정]

 

- 2차원 배열 헷갈리지 말자!! -

 

arr[행][열] 발음하는 순서대로 생각하면 된다 (행의 인덱스 / 열의 인덱스)

• 다만 행 인덱스는 세로줄을 보고 판단 열의 인덱스는 가로줄을 보고 판단
  
  
• 행의 개수 = 세로로 나열된 원소의 개수
  열의 개수 = 가로로 나열된 원소의 개수
  
  단순히 행은 가로줄을 의미하니까 가로줄의 원소의 개수와 같다고 생각해선 안된다!

 

x이동과 y이동은 좌표가 아닌 배열의 형식으로 생각한다

 

char[][] arr = {
    {'O', 'S', 'O'},
    {'O', 'X', 'O'},
    {'O', 'O', 'O'}
};

 

여기서 S의 위치는 좌표형식으로 본다면 높이가 바뀐 것이 아니기 때문에 (1,0) 이다 

하지만 배열의 형식으로 본다면 0번째 행의 1번째 열이므로 arr[1][0]이 맞다

고로 x를 가로의 이동이 아닌 행의 이동 (세로이동)으로 생각하고

y를 세로의 이동이 아닌 열의 이동 (가로이동)으로 생각한다

 

 

1. 좌표 모두 수집해서 최소와 최대값 뽑아내기

• 좌표의 최소 최대를 안다면 그 모든 것들을 포함한 최대 드래그 범위 또한 알 수 있다
• 예로 #이 arr[0][1] / arr[1][2] / arr[2][3] 이라면
  행 최소값 0 / 열 최소값 1
  행 최대값 2 / 열 최대값 3
  0,1 꼭짓점에서 3,4 꼭짓점까지 드래그한다
• 꼭짓점이라서 마지막 지점은 꼭 +1 씩 해주기

 

2. # 지점의 좌표 꺼내서 저장

• [코드1] arr[i]=wallpaper[i].toCharArray();
  • 2차원 배열을 모두 생성 후 #좌표 꺼내기
• [코드2] if (wallpaper[i].charAt(j) == '#')
  • 배열 생성 없이 #좌표 꺼내기 

 

3. Math 또는 sort를 통해서 결과 출력

• Math min / max 출력
• Collections.sort 로 정렬 후 처음이나 마지막꺼 출력

 

 

[코드1]

import java.util.*;

class Solution {
    public int[] solution(String[] wallpaper) {
        char arr[][] = new char[wallpaper.length][wallpaper[0].length()];
        ArrayList<Integer> x = new ArrayList<>();
        ArrayList<Integer> y = new ArrayList<>();
        
        for(int i=0;i<wallpaper.length; i++){
            arr[i]=wallpaper[i].toCharArray();
            for(int j=0; j<wallpaper[i].length();j++){
                if(arr[i][j]=='#'){
                    x.add(i);
                    y.add(j);
                }
            }
        }
        
        Collections.sort(x);
        Collections.sort(y);

        int[] result = new int[4];
        
        result[0]=x.get(0);
        result[1]=y.get(0);
        result[2]=x.get(x.size()-1)+1;
        result[3]=y.get(y.size()-1)+1;
        
        return result;
        
    }
}

 

 : public int[] solution(String[] wallpaper) {  입력받기
        char arr[][] = new char[wallpaper.length][wallpaper[0].length()];  문자 2차원 배열 
        ArrayList<Integer> x = new ArrayList<>();  x 배열
        ArrayList<Integer> y = new ArrayList<>();  y 배열
        
        for(int i=0;i<wallpaper.length; i++){  입력 한묶음만큼 반복
            arr[i]=wallpaper[i].toCharArray();  2차원 배열 생성
            for(int j=0; j<wallpaper[i].length();j++){  입력 한묶음의 원소 개수만큼 반복
                if(arr[i][j]=='#'){  # 지점 좌표 출력
                    x.add(i);
                    y.add(j);
                }
            }
        }
        
        Collections.sort(x);  정렬
        Collections.sort(y);  정렬

        int[] result = new int[4];  출력배열
        
        result[0]=x.get(0);  행 최소값 출력 
        result[1]=y.get(0);  열 최소값 출력
        result[2]=x.get(x.size()-1)+1;  행 최대값 + 1 출력 
        result[3]=y.get(y.size()-1)+1;  열 최대값 + 1 출력
        
        return result; 정답
        
    }

 

 

[코드2_좀 더 간단]

import java.util.*;

class Solution {
    public int[] solution(String[] wallpaper) {
        int x_min = Integer.MAX_VALUE;
        int x_max = Integer.MIN_VALUE;
        
        int y_min = Integer.MAX_VALUE;
        int y_max = 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)=='#'){
                    x_min=Math.min(x_min,i);
                    y_min=Math.min(y_min,j);
                    x_max=Math.max(x_max,i);
                    y_max=Math.max(y_max,j);
                }
            }
        }
        
        
        return new int[]{x_min, y_min, x_max+1, y_max+1};
        
    }
}

 

 : public int[] solution(String[] wallpaper) {  입력받기
        int x_min = Integer.MAX_VALUE;
        int x_max = Integer.MIN_VALUE;
        
        int y_min = Integer.MAX_VALUE;
        int y_max = 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)=='#'){  그때그때마다 # 나온 좌표 출력
                    x_min=Math.min(x_min,i);  행 최소값
                    y_min=Math.min(y_min,j);  열 최소값
                    x_max=Math.max(x_max,i);  행 최대값
                    y_max=Math.max(y_max,j);  열 최대값
                }
            }
        }
        
        
        return new int[]{x_min, y_min, x_max+1, y_max+1};  정답 배열 바로 만들어 출
        
    }

 

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

프로그래머스