프로래머스 Lv1 [PCCE 기출문제] 10번 공원 문제

• 프로래머스 Lv1 무제[PCCE 기출문제] 10번 공원 문제
  • 해당 문제의 난이도 상승 원인
    • 정사각형 영역 전체가 비어있는지 확인이 필요
    • 가장 큰 돗자리부터 확인
  • 해당 문제를 해결한 방법
    • 최대 x/y 값을 구하고 그 안에서 범위를 탐색
    • 만족하는 경우를 찾으면 바로 종료하여 불필요한 탐색은 일어나지 않게 함
    • 가능한 돗자리의 경우의 수들을 먼저 내림차순으로 정렬하여 최대 크기 돗자리가 선택되게 끔 설정
  • 처음 방식에서 변경한 방식
    • 처음
      • 모든 위치를 기준으로 최대 정사각형 크기를 계산하려고 시도
    • 변경
      • 이전 코드에선 중복작업이 많이 이를 제거하고, 하나라도 만족할 시 바로 반환하여 값이 나오도록 변경
  • 문제의 핵심
    • 들어온 데이터를 정렬시켜서 큰 값부터 탐색하게 하는 접근
  • 이 문제의 목적
    • 데이터 전처리의 중요성 알림
    • 불필요한 계산은 막도록 초기 설계의 중요성 학습

import java.util.Arrays;
import java.util.Collections;
class Park {
    public int solution(int[] mats, String[][] park) {
        int answer = -1;

        // 매트 길이 긴 순으로 내림차순 정렬
        int mal = mats.length; //matArrLength
        Integer[] transMats = Arrays.stream(mats).boxed().toArray(Integer[]::new);
        Arrays.sort(transMats, Collections.reverseOrder());

        int yl = park.length; // y len
        int xl = park[0].length; // x len

        for(Integer v : transMats){
            if(v == null){
                continue; // null 검사
            }

            int val = v; // Integer -> int

            if(val > yl || val > xl) continue;

            for(int y = 0; y + val <= yl; y++){
                for(int x = 0; x + val <= xl; x++){
                    boolean sign = true;
                    for(int ystart = y; ystart < (y + val) && sign; ystart++){
                        for(int xstart = x; xstart < (x + val); xstart++){
                            if(!park[ystart][xstart].equals("-1")){
                                sign = false;
                                break;
                            }
                        }
                    }
                    if(sign){
                        return val;
                    }
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        int[] mats = {5, 3, 2};
        String[][] park = {
                {"A", "A", "-1", "B", "B", "B", "B", "-1"},
                {"A", "A", "-1", "B", "B", "B", "B", "-1"},
                {"-1", "-1", "-1", "-1", "-1", "-1", "-1", "-1"},
                {"D", "D", "-1", "-1", "-1", "-1", "E", "-1"},
                {"D", "D", "-1", "-1", "-1", "-1", "-1", "F"},
                {"D", "D", "-1", "-1", "-1", "-1", "E", "-1"}
        };

        Park p = new Park();

        System.out.println("결과 : " + p.solution(mats, park));
    }
}