재밌고 어려운 IT를 이해해보자~!
소유주가 다른 땅에서 가장 큰 'ㄷ' 모양 찾기 본문
소유주가 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