문제
30년동안 열심히 돈을 모은 상근이는 드디어 아파트 하나를 구매했다. 상근이는 친구들을 최대한 많이 초대해 집들이를 하려고 한다.
집들이를 하기 전에 모든 사람이 앉을 수 있는 직사각형 식탁을 하나 사려고 한다. 식탁에 앉을 수 있는 사람의 수는 식탁의 둘레 길이와 같다. (네 변의 길이의 합)
상근이는 되도록 큰 식탁을 구매해서 되도록 많은 사람들과 같이 저녁을 먹을 수 있게 하려고 한다. 식탁은 항상 아파트의 변에 평행하게 놓아야 한다.
아파트의 레이아웃이 주어졌을 때, 상근이가 초대할 수 있는 사람의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 아파트의 크기를 나타내는 R과 C가 주어진다. (1 ≤ R, C ≤ 400)
다음 R개 줄에는 C개의 문자가 주어지며, 빈 칸은 '.', 막힌 칸은 'X'로 주어진다.
상근이는 오직 빈 칸에만 식탁을 놓을 수 있다. 또, 사람의 크기는 매우 작다고 생각하면 된다.
출력
첫째 줄에 상근이가 초대할 수 있는 사람의 수를 출력한다.
예제 입력 1
2 2
..
..
예제 출력 1
7
예제 입력 2
4 4
X.XX
X..X
..X.
..XX
예제 출력 2
9
예제 입력 3
3 3
X.X
.X.
X.X
예제 출력 3
3
풀이 1. 완전 탐색
우선 가장 빠르게 생각할 수 있는 풀이인 완전 탐색 풀이 입니다. 모든 직사각형을 확인해서 최대 사람 수를 구하는 방식입니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
char[][] grid = new char[R][C];
for (int i = 0; i < R; i++) {
grid[i] = br.readLine().toCharArray();
}
int ans = 0;
for (int r1 = 0; r1 < R; r1++) {
for (int c1 = 0; c1 < C; c1++) {
for (int r2 = r1; r2 < R; r2++) {
for (int c2 = c1; c2 < C; c2++) {
boolean ok = true;
for (int i = r1; i <= r2 && ok; i++) {
for (int j = c1; j <= c2; j++) {
if (grid[i][j] == 'X') {
ok = false;
break;
}
}
}
if (ok) {
int h = r2 - r1 + 1;
int w = c2 - c1 + 1;
int a = 2 * (h + w) - 1;
ans = Math.max(ans, a);
}
}
}
}
}
System.out.println(ans);
}
}정말 단순하게 모든 좌표를 돌아서 (4중 for문;;) 중요한 2*(h+w) - 1(자기 자신)의 최댓값을 갱신하는 풀이입니다.
시간복잡도가 O(R^2 * C^2) 로 당연히 시간 초과가 나게 됩니다.
완전 탐색을 구현하고 나니 직사각형 내부 검사를 최적화하는 방법이 필요하다 생각이 들었습니다.
풀이 2. 누적합
행 구간을 top ~ bottom 을 하나 고정하면 높이가 h = bottom - top + 1로 정해집니다.
그 후 각 열 j에 대해,
top~bottom구간에X가 하나도 없으면 사용 가능- 하나라도 있으면 사용 불가
로 판단하면 됩니다.
이를 위해 열 방향 누적합을 만들게 되는데
sum[i + 1][j] = 0행부터 i행까지 j열에 있는 X 개수이렇게 두면 top ~ bottom 구간을 j열에 X가 있는지 여부를
sum[bottom + 1][j] - sum[top][j]로 O(1)으로 알 수 있습니다.
이러면 행 시작점을 top : R, 행 끝점 bottom : R, 각 경우 스캔 : C 로 O(R^2 * C)의 시간복잡도가 됩니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
char[][] grid = new char[R][C];
for (int i = 0; i < R; i++) {
grid[i] = br.readLine().toCharArray();
}
int[][] sum = new int[R + 1][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
sum[i + 1][j] = sum[i][j] + (grid[i][j] == 'X' ? 1 : 0);
}
}
int ans = 0;
for (int top = 0; top < R; top++) {
for (int bottom = top; bottom < R; bottom++) {
int h = bottom - top + 1;
int w = 0;
for (int j = 0; j < C; j++) {
int block = sum[bottom + 1][j] - sum[top][j];
if (block == 0) {
w++;
int a = 2 * (h + w) - 1;
ans = Math.max(ans, a);
} else {
w = 0;
}
}
}
}
System.out.println(ans);
}
}
풀이 3. 모노톤 스택
또 다른 방식으로 각 행을 바닥으로 생각하고 각 열마다 위로 연속된 빈 칸의 개수를 height[j]로 관리합니다.
예를 들어 현재 행이 i일 때
grid[i][j] == '.'이면height[j]++grid[i][j] == 'X'이면height[j] = 0
이렇게 판단하면 height[jh]는 현재 행 기준으로 막대 그래프 모양이 그려집니다.
이 막대 그래프에서 만들 수 있는 직사각형 중 최댓값을 찾으면 정답이 됩니다.
각 위치에서 왼쪽으로 처음 나오는 더 작은 높이와 오른쪽으로 처음 나오는 더 작은 높이를 찾아서 너비를 구하게 됩니다.
이 두 경계를 알면 j를 최소 높이로 하는 최대 너비를 바로 구할 수 있게 됩니다.
l[j] : j의 왼쪽에서 처음 만나는 더 작은 높이의 인덱스
r[j] : j의 오른쪽에서 처음 만나는 더 작은 높이의 인덱스
그러면 l[j] + 1 부터 r[j] - 1 까지는 모두 height[j] 이상이므로, 이 구간 전체를 너비로 사용할 수 있습니다.
w = r[j] - l[j] - 1;그리고 초대 가능한 사람 수는
2 * (height[j] + w) - 1로 구하게 됩니다.
이때 l, r을 매번 선형 탐색으로 구하면 또 C만큼 걸리기 때문에 높이가 증가하는 형태를 유지하는 모노톤 스택을 활용할 수 있습니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
char[][] grid = new char[R][C];
for(int i = 0; i < R; i++) {
grid[i] = br.readLine().toCharArray();
}
int[] height = new int[C];
int ans = 0;
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++) {
if(grid[i][j] == '.') height[j]++;
else height[j] = 0;
}
int[] l = new int[C];
int[] r = new int[C];
Deque<Integer> s = new ArrayDeque<>();
for(int j = 0; j < C; j++) {
while(!s.isEmpty() && height[s.peek()] >= height[j]) {
s.pop();
}
l[j] = s.isEmpty() ? -1 : s.peek();
s.push(j);
}
s.clear();
for(int j = C - 1; j >= 0; j--) {
while(!s.isEmpty() && height[s.peek()] >= height[j]) {
s.pop();
}
r[j] = s.isEmpty() ? C : s.peek();
s.push(j);
}
for(int j = 0; j < C; j++) {
if(height[j] == 0) continue;
int w = r[j] - l[j] - 1;
int a = 2 * (height[j] + w) - 1;
ans = Math.max(ans, a);
}
}
System.out.println(ans);
}
}이러면 아마...O(R*C)라 생각했는데.....
메모리만 더 쓰고 시간이 똑같더라구요!
왜 시간이 그대로지?!!?!?!?!??
...혹시 아신다면 댓글로 지혜를 나눠주십쇼.
마무리
요즘 알고리즘 풀면서 최대한 다양한 방식으로 풀어보려 하는데 단순 구현에서 점점 최적화 하는 방식을 떠올리는 것이 뭔가 더 어렵게 느껴집니다.
이전엔 사고의 흐름이 이거 맞겠지~? 하는 느낌이라면 요즘엔 진짜 검산하고 들어가는 느낌이라 정확도는 높은데 시간이 더 걸리는 느낌.
장단점이 있는 것 같습니다.
