문제
풀이
처음에 접근해서 고민할 때 tree에 뭘 저장해야 하나 모르겠어서 최소 넓이, 최대 넓이같은 걸 생각해봤다. 아무리 생각해도 적절한게 생각이 안 나서 다른 블로그 풀이를 참고했다.. 범위에서의 최소 높이의 인덱스를 저장한다는 것만 블로그에서 힌트로 얻고, 나머지 풀이는 내가 생각해내서 코드를 짜보았다.
설명
heights[]: 주어진 입력을 Long타입으로 받아 저장한다.tree[]: 주어진 구간의heights중 최솟값의 인덱스를 저장한다.
initTree()
- 재귀의 종료 조건은
start == end, 즉 리프 노드일 때다.tree[node]에 왼쪽과 오른쪽 자식 노드 중heights에서의 값이 더 작은 놈을 저장한다. 이를 코드로 나타내면 아래와 같다.
tree[node] = (heights[tree[node * 2]] < heights[tree[node * 2 + 1]] ? tree[node * 2] : tree[node * 2 + 1]);
calcMaxArea()
left와 right 사이에서 만들 수 있는 직사각형의 최대 넓이를 구한다.
- 현재 범위에서의 최대의 높이를
getMaxHeightIndex()를 통해 구하고max에 그 때의 넓이를 저장한다.- 최대 높이
index를 기준으로, 그 왼쪽과 오른쪽 범위에서 만들 수 있는 최대 넓이를 재귀적으로 구한다.
- 재귀 호출했을 때,
left > right이면 범위가 유효하지 않으므로 0을 반환하고left == right이면 바로 그 높이를 반환한다.- 현재
index, 그 왼쪽, 오른쪽 넓이를 비교해서max를 최댓값으로 갱신한다.
getMaxHeightIndex()
left와right사이에서 만들 수 있는 직사각형의 최대 높이를 구한다.start와end는node가 포함하는 인덱스의 범위를 의미한다.
left-right와 start-end를 활용해 값을 구해야 하는데, 3가지 경우로 생각할 수 있다.
start-end와left-right가 겹치는 부분이 아예 없는 경우
→ 유효하지 않으므로INVALID반환start-end가left-right에 완전히 포함되는 경우
→ 유효하므로tree[node]반환start-end와left-right가 부분적으로 겹치는 경우
→ 재귀적으로 재탐색
재탐색하는 경우는 아래와 같은 순서로 작동한다.
- 두 자식 노드에 대해 재귀 호출해서
leftMax와rightMax를 구한다.- 둘 중 하나라도
INAVLID한 경우 나머지 값을 반환한다.- 둘다 유효한 값인 경우,
heights가 더 작은 노드값을 반환한다.
삽질
별 황당무계한 실수로 1시간정도 삽질을 했다! 억울해! 채점 20퍼에서 계속 오답이 떠서 앞 문제에서 실수했던 부분을 중심으로 다시 살펴보고 로직도 다시 검토했지만 고쳐지지가 않았다.
그러다가 테케로 2 1 10000를 넣으니 답이 10000이 아닌 2가 나왔고, 잘못된 부분을 발견할 수 있었다. 문제는 calcMaxArea()에서 heights[left]가 아닌 heights[tree[left]]를 리턴한 것... 또르륵... 이거 고쳤더니 바로 통과됐다...ㅎㅎ...
코드
import java.io.*;
public class Main {
private static final String FINISH = "0";
private static final int INVALID = -1;
private static int n;
private static long[] heights;
private static int[] tree;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] line;
while ((line = br.readLine().split(" ")).length > 1) {
n = Integer.parseInt(line[0]);
heights = new long[n + 1];
tree = new int[(n + 1) * 4];
for (int i = 1; i <= n; i++) heights[i] = Long.parseLong(line[i]);
initTree(1, 1, n);
bw.append(String.valueOf(calcMaxArea(1, n))).append("\n");
}
br.close();
bw.close();
}
private static void initTree(int node, int start, int end) {
if (start == end) {
tree[node] = start;
return;
}
int mid = (start + end) / 2;
initTree(node * 2, start, mid);
initTree(node * 2 + 1, mid + 1, end);
tree[node] = (heights[tree[node * 2]] < heights[tree[node * 2 + 1]] ? tree[node * 2] : tree[node * 2 + 1]);
}
private static long calcMaxArea(int left, int right) {
if (left > right) return 0;
if (left == right) return heights[left];
int index = getMaxHeightIndex(1, 1, n, left, right);
long max = heights[index] * (long) (right - left + 1);
max = Math.max(max, calcMaxArea(left, index - 1));
max = Math.max(max, calcMaxArea(index + 1, right));
return max;
}
private static int getMaxHeightIndex(int node, int start, int end, int left, int right) {
if (start > right || end < left) return INVALID;
if (start >= left && end <= right) return tree[node];
int mid = (start + end) / 2;
int leftMax = getMaxHeightIndex(node * 2, start, mid, left, right);
int rightMax = getMaxHeightIndex(node * 2 + 1, mid + 1, end, left, right);
if (leftMax == INVALID) return rightMax;
if (rightMax == INVALID) return leftMax;
return (heights[leftMax] < heights[rightMax] ? leftMax : rightMax);
}
}