재밌고 어려운 IT를 이해해보자~!

소유주가 다른 땅에서 가장 큰 'ㄷ' 모양 찾기 본문

알고리즘

소유주가 다른 땅에서 가장 큰 'ㄷ' 모양 찾기

언제나즐거운IT 2024. 10. 24. 22:14

소유주가 A~Z까지 다른 땅에서 같은 소유주로 이루어진 'ㄷ' 모양 (모양의 방향은 상관없음) 땅을 찾는 알고리즘을 알아보자..!

 

방향에 상관없이 'ㄷ'자인지 확인하는 과정을 생각해내는게 쉽지않다..

 

 

public class DShapeFinder {
    public static void main(String[] args) {
        String[] land1 = {"AAA", "AAA", "AAA"};
        String[] land2 = {"BAA", "ABB", "ABB", "AAA"};
        String[] land3 = {"BAAAD", "AAAAA", "ABBAA", "AAAAA"};

        System.out.println(findMaxDArea(land1)); // 9
        System.out.println(findMaxDArea(land2)); // -1
        System.out.println(findMaxDArea(land3)); // 11
    }

    public static int findMaxDArea(String[] land) {
        int rows = land.length;
        int cols = land[0].length();
        int maxArea = -1;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                char owner = land[r].charAt(c);
                if (owner == ' ') continue; // 방문한 땅은 무시

                int leftLength = getLeftLength(land, r, c, owner);
                int downLength = getDownLength(land, r, c, owner);

                if (leftLength >= 3 && downLength >= 2) {
                    int area = leftLength * 2 + downLength - 2; // 'ㄷ'자 면적 계산
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }

    private static int getLeftLength(String[] land, int r, int c, char owner) {
        int length = 0;
        while (c - length >= 0 && land[r].charAt(c - length) == owner) {
            length++;
        }
        return length;
    }

    private static int getDownLength(String[] land, int r, int c, char owner) {
        int length = 0;
        while (r + length < land.length && land[r + length].charAt(c) == owner) {
            length++;
        }
        return length;
    }
}

'알고리즘' 카테고리의 다른 글

[백준] 2493  (0) 2024.11.27
[백준] 6198  (0) 2024.11.27
타일채우기 재귀 알고리즘  (0) 2024.08.10
코딩테스트 풀어보기!  (0) 2024.05.28
[백준] 2775  (0) 2024.05.26
Comments