[Java 자바] 프로그래머스 Lv 1 - [PCCE 기출문제] 10번 / 공원

 

 

코딩테스트 연습 | 프로그래머스 스쿨

 

목차

1. 문제 설명
2. 입출력 예시
3. 문제 풀이

 

 

---

1. 문제 설명

 

 

728x90

 

문제 설명

지민이는 다양한 크기의 정사각형 모양 돗자리를 가지고 공원에 소풍을 나왔습니다. 공원에는 이미 돗자리를 깔고 여가를 즐기는 사람들이 많아 지민이가 깔 수 있는 가장 큰 돗자리가 어떤 건지 확인하려 합니다. 예를 들어 지민이가 가지고 있는 돗자리의 한 변 길이가 5, 3, 2 세 종류이고, 사람들이 다음과 같이 앉아 있다면 지민이가 깔 수 있는 가장 큰 돗자리는 3x3 크기입니다.

지민이가 가진 돗자리들의 한 변의 길이들이 담긴 정수 리스트 mats, 현재 공원의 자리 배치도를 의미하는 2차원 문자열 리스트 park가 주어질 때 지민이가 깔 수 있는 가장 큰 돗자리의 한 변 길이를 return 하도록 solution 함수를 완성해 주세요. 아무런 돗자리도 깔 수 없는 경우 -1을 return합니다.

 

 

제한사항

• 1 ≤ mats의 길이 ≤ 10
• 1 ≤ mats의 원소 ≤ 20
• mats는 중복된 원소를 가지지 않습니다.
• 1 ≤ park의 길이 ≤ 50
• 1 ≤ park[i]의 길이 ≤ 50
• park[i][j]의 원소는 문자열입니다.
• park[i][j]에 돗자리를 깐 사람이 없다면 "-1", 사람이 있다면 알파벳 한 글자로 된 값을 갖습니다.

 

 

 

 

---

2. 입출력 예시

 

 

 

 

입출력 예시

#1 

지문과 동일

 

 

 

 

 

---

3. 문제 풀이

반응형

 

문제 풀이

class Solution {
    public int solution(int[] mats, String[][] park) {
        int answer = -1;
        int[][] maxSize = new int[park.length][park[0].length];
        int canSize = 0;
        
        // 1. 공원의 빈 공간의 최대 크기 구하기
        for(int i=0; i<park.length; i++){
            for(int j=0; j<park[0].length; j++){
                
                // 1.1. 빈공간 찾으면, 왼쪽/위쪽/대각선이 빈공간이면 1씩 더해가기
                if(park[i][j].equals("-1")){
                    if(i==0 || j==0){
                        maxSize[i][j] = 1;
                    } else {
                        maxSize[i][j] = Math.min(Math.min(maxSize[i][j-1], maxSize[i-1][j]), maxSize[i-1][j-1]) + 1;
                    }
                    
                    // 1.2. 최대 크기 저장
                    canSize = Math.max(canSize, maxSize[i][j]);
                }
            }
        }
        
        // 2. 내가 가지고 있는 돗자리 중 깔 수 있는 가장 큰 돗자리 찾기
        for(int i=0; i<mats.length; i++){
            if(mats[i] <= canSize){
                answer = Math.max(answer, mats[i]);
            }
        }
        
        return answer;
    }
}