[테코테코1.5 1-08] 공원

💡테코테코 시즌 1.5 1회 모임 off-site 문제 풀이입니다. (2025.01.12)

 

문제

 

출처: 프로그래머스 - PCCE 기출문제 10. 공원

 

내용

 

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

 

 

 

 

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

 

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

어떤 알고리즘을 적용하려 했나요?

 

DP, Dynamic Programming을 이용하려 한다.

 

적용 근거는 무엇인가요?

프로그래머스 문제 중 가장 큰 정사각형 찾기 와 유사하기 때문이다.

 

문제 풀이 과정에서 해당 알고리즘을 어떻게 코드로 구현하려 했나요?

 

풀이 방식의 이미지는 이 글을 참고하면 된다.

-1을 가진 최대 정사각형을 찾아 한 변의 길이가 2, 3, 5 중 가능한 큰 값을 반환하면 된다.

 

1. DP 배열 선언. (아니면 주어진 2차원 배열 그대로 사용해도 됨)
    1. 첫 행은 그대로 지나감
    2. 두 번째 행부터 탐색하는 칸 기준으로 좌, 상, 좌상 탐색
        1. 탐색값이 1일 경우 정사각형 만들 수 있는 갯수를 기록
        2. 숫자가 2 이상일 경우 좌, 우, 좌우 탐색 기준으로 해당 변의 길이를 가진 정사각형을 만들 수 있다고 이해하면 됨
    3. 아래 행까지 만들 수 있는 정사각형의 변의 길이를 누적함
        1. 최대 길이 갱신
2. 최대 정사각형의 변의 길이 2, 3, 5 중 반환

 

 

풀이

풀이 시간

시작 시각	종료 시각	총 소요 시간
22:02	22:37	35분

 

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

 

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

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

mats	park	result
[5,3,2]	[["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"]]

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

1. DP 배열 선언. (아니면 주어진 2차원 배열 그대로 사용해도 됨)
    1. 첫 행은 그대로 지나감
    2. 두 번째 행부터 탐색하는 칸 기준으로 좌, 상, 좌상 탐색
        1. 탐색값이 1일 경우 정사각형 만들 수 있는 갯수를 기록
        2. 숫자가 2 이상일 경우 좌, 우, 좌우 탐색 기준으로 해당 변의 길이를 가진 정사각형을 만들 수 있다고 이해하면 됨
    3. 아래 행까지 만들 수 있는 정사각형의 변의 길이를 누적함
        1. 최대 길이 갱신
2. 최대 정사각형의 변의 길이 2, 3, 5 중 반환

solution(int[] mats, int[][] park) {
    int maxLength = 0;
    for (int i ; park.length) {
        for (int j ; park[0].length) {
            // 1 찾기
                // 좌, 상, 좌상 확인하고 +1 해주기
                // 해당 칸 = min + 1
            // maxLength 갱신
        }
    }

    int answer = -1;
    for (int m : mats) {
        // m <= maxLength 일 경우 answer 갱신
    }
    return answer;
}

 

 

구현

class Solution {
    public int solution(int[] mats, String[][] park) {
        int n = park.length;
        int m = park[0].length;
        int[][] dp = new int[n][m];

        // 계산 편하게 하기 위해 String -> int 변환
        for (int i = 0;i < n; i++) {
            for (int j = 0;j < m; j++) {
                // -1 찾기
                dp[i][j] = park[i][j].equals("-1") ? 1 : 0;
            }
        }

        int maxLength = 0;
        for (int i = 1;i < n; i++) {
            for (int j = 1;j < m; j++) {
                if (dp[i][j] > 0) {
                    // 좌, 상, 좌상 확인하고 +1 해주기
                    int min = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                    dp[i][j] = min + 1;
                    // maxLength 갱신
                    maxLength = Math.max(maxLength, min + 1);
                }
            }
        }

        int answer = -1;
        for (int mat : mats) {
            // answer < mat <= maxLength 일 경우 answer 갱신
            if (answer < mat && mat <= maxLength) {
                answer = mat;
            }
        }
        return answer;
    }
}

 

 

복기하기

답안과 나의 풀이를 비교해보세요

• 돗자리를 max 값부터 탐색하는 게 더 빨리 끝난다.
• 입력값 분석해보면 전체탐색도 가능하다. (n^2 * m^2 의 경우 2500만임)

요약하기

• 결국 많이 풀면 응용이 된다.