프로그래머스 | LV.1 바탕화면 정리 - 단순 구현 문풀 (Java)

⬛ 프로그래머스 | LV.1 바탕화면 정리 - 단순 구현 문풀

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

프로그래머스

문제설명

예시 설명

제한 사항

---

💚문제 접근 방식

• 레벨 1 문제여서 복잡하게 생각하지 않고, 최대한 문제 내용대로 이해하는 데 초점을 맞춰서 풀었다.
• S좌표에서 E좌표로 드래그해서 모든 파일 선택하는 게 목표인 문제이다.
• 좌표 상은 격자표 위의 (x,y) 좌표여서,시작점은 상관없는데, E 끝점에는 +1씩 처리해줘야 문제대로 풀린다.

S→E 로 드래그 : 가장 왼쪽&위쪽 파일 아우르는 좌표 → 가장 오른쪽&아래쪽 파일 아우르는 좌표로 생각하고 품

→ 결국 S 시작점은 (행 최소, 열 최소) , E 끝점은 (행 최대, 열 최대) 로 지칭하면 된다는 결론이 나온다.

→ 2차원 map에 입력값 중 ‘#’ 파일 위치들을 담으면서, 파일의 i, j 좌표를 x 최소, y + 1최소, x최대, y+1 최대 갱신해가며 담고 최종 갱신값을 리턴하면 해결되는 문제이다.

💚 제출 코드 - 최종

import java.util.*;

class Solution {
    private static char[][] map;
    //솔루션 함수 
    public int[] solution(String[] wallpaper) {
        int[] answer;
        
        int N = wallpaper.length;
        int M = wallpaper[0].length();
        
        map = new char[N][M];
        
        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<N; i++){
            for(int j=0; j<M; j++){
                map[i][j] = wallpaper[i].charAt(j);
                if(map[i][j] == '#'){
                    minX = Math.min(minX, i);
                    minY = Math.min(minY, j);
                    maxX = Math.max(maxX, i+1);
                    maxY = Math.max(maxY, j+1);
                }
            }
        }
    
        return new int[] {minX, minY, maxX, maxY};
    }
}

💚 제출 코드 - 최초 제출

• 첫 제출 때는 # 파일 위치 발견할 때마다, pQ에 x,y 좌표를 담으면서 각각 오름차순 내림차순 정렬해서 맨 앞에 poll()한 값으로 세팅해야지 하고 풀었고 맞긴 했는데, 솔직히 pQ를 4개나 쓸 필요가 있었나 싶다.
• 어차피 최대, 최소만 쓸 건데, 그때 그때 갱신된 값을 간략히 쓰는 게 더 낫다는 생각이 들었다.
• 최종 제출 풀이로 푸는 게 더 간단하고 명확해 보인다.

import java.util.*;

class Solution {
    private static char[][] map;
    //솔루션 함수 
    public int[] solution(String[] wallpaper) {
        int[] answer = new int[4];
        
        int N = wallpaper.length;
        int M = wallpaper[0].length();
        
        map = new char[N][M];
        /* 너무 지저분함 Deque나 다른 거 사용할 것 !!!!!!!!!
        */
        PriorityQueue<int[]> xQ = new PriorityQueue<> ((a, b) -> a[0] - b[0]); //x좌표 최소 우선순위
        PriorityQueue<int[]> yQ = new PriorityQueue<> ((a, b) -> a[1] - b[1]); //y좌표 최소 우선순위 
        PriorityQueue<int[]> xMaxQ = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        PriorityQueue<int[]> yMaxQ = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                map[i][j] = wallpaper[i].charAt(j);
                if(map[i][j] == '#'){
                    xQ.offer(new int[] {i, j});
                    yQ.offer(new int[] {i, j}); 
                    xMaxQ.offer(new int[] {i, j});
                    yMaxQ.offer(new int[] {i, j});
                }
            }
        }
        
        if(xQ.size() == 1){
            int[] tmp = xQ.poll();
            answer[0] = tmp[0];
            answer[1] = tmp[1];
            answer[2] = tmp[0] + 1;
            answer[3] = tmp[1] + 1;
            
            return answer;
        }
        
        int[] minX = xQ.poll();
        int[] minY = yQ.poll();
        
        answer[0] = minX[0];
        answer[1] = minY[1];
        
        int[] maxX = xMaxQ.poll();
        int[] maxY = yMaxQ.poll();
        
        answer[2] = maxX[0] +  1;
        answer[3] = maxY[1] + 1;
        
        return answer;
    }
}

---

💚 시간복잡도

시간복잡도는 wallpaper 내부 값을 이중 for문을 도는데 각각 50이 최대라서 2500 이면 크게 시간 잡아먹지 않는다.

💚 회고

lv1 문제는 보통 단순 구현이 많다. 단순 구현 시 최대한 간략하고 명확한 접근법을 떠올리는 게 중요하다. 연습을 많이 하자.