항하99 TIL 3일차(바탕화면 정리/프로그래머스)

문제                    

프로그래머스

 

 

1 번째 시도                            

 

아이디어: 그리드 / 현재 상황 속에서 최적인 해 구하기

• 정렬하지 않은 배열을 다 돈다.
• x1,y1의 최솟값을 구하고 x2,y2의 최댓값을 업데이트 해간다.

import java.util.*;

class Solution {
    public int[] solution(String[] wallpaper) {
        int height = wallpaper.length;
        int width = wallpaper[0].length();

        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<height; i++) {
            for(int j=0; j < width; j++) {
                if(wallpaper[i].charAt(j) == '#') {
                 lux =  Math.min(lux, i); 
                 luy =   Math.min(luy, j);
                 rdx =   Math.max(rdx, i);
                 rdy =   Math.max(rdy, j);
                }
            }
        }

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

한 방에 성공했다!

오늘도 어김없이 성공했을지라도 다른 사람의 코드를 보며 배울 점을 더 얻어가겠다.

그럴려고 했지만 다른 사람의 풀이도 다 나와 같고 특별한 풀이가 안 보여서 이번 문제는 이쯤으로 넘어가겠다.

+) 이번 문제가 그리드 알고리즘이 맞나?

그리드 알고리즘이란 어떤 문제에 대해서 탐욕적으로 즉 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"으로 문제를 해결하는 방법이다. for문을 돌면서 최솟값과 최댓값을 찾음으로 그리드 알고리즘 문제라고 명했다. 이 문제가 그리드 알고리즘 문제인지 정확한 기준이 안세워진다.