▼ What ?
이번에 해결한 문제는 2차원 배열의 행과 열을 다루는 문제이다.
▼ 스카이라인
문제 정보
N 격자판에 N*N개의 도시 빌딩의 높이정보가 주어집니다.
도시를 앞에서 봤을 때 스카이 라인은 왼쪽부터 해서 [7, 8, 9, 8]의 높이정보로 보이고, 옆에 서 보면 위쪽에서부터 해서 [7, 9, 5, 8]입니다. 매개변수 board에 도시의 각 빌딩의 높이 정보가 주어지면 도시의 스카이라인은 변함이 없이 각 빌딩의 높이를 최대한 높이고자 합니다. 각 빌딩의 높이를 증가시킬 수 있는 최대 높이의 합을 구하는 프로그램을 작성하세요.
제한 사항
- board.length의 길이는 100을 넘지 않는 홀수입니다.
입출력 예
어떻게 해결해야 할까 ?
- 정면과 측면에서 바라본 스카이라인보다 높아지지 않는 선에서 건물들의 높이를 최대한 증가시킬 수 있는 경우를 생각하면 된다
- 정면 스카이라인에서 각 건물의 최대 높이를 계산한다
- 측면 스카이라인에서 각 건물의 최대 높이를 계산한다
- 각 건물에 대해 정면도와 측면도에서 최대 높이 중 최소값을 구하고 건물의 현재 높이를 빼서 잠재적인 높이 증가량을 찾으면 된다
- 마지막으로 모든 건물의 잠재적인 높이 증가를 합산합니다
해결 코드
public class Training_Skyline {
public int solution(int[][] board){
int N = board.length;
int[] frontMax = new int[N];
int[] sideMax = new int[N];
for(int row = 0; row < N; row++) {
for(int col = 0; col < N; col++) {
// 전면 (행을 기준으로)
if(board[row][col] > frontMax[col]) frontMax[col] = board[row][col];
// 측면 (열을 기준으로)
if(board[row][col] > sideMax[row]) sideMax[row] = board[row][col];
}
}
int answer = 0;
for(int row = 0; row < N; row++) {
for(int col = 0; col < N; col++) {
// 전면과 측면에서 바라본 스카이라인 중 더 낮은 스카이라인을 각 건물의 최대 높이로 설정
answer += Math.min(frontMax[col], sideMax[row]) - board[row][col];
}
}
return answer;
}
}
▼ 정리
- 이번 문제는 문제를 이해하는 것이 관건이었던 문제였던 것 같다
( 전면과 측면에서 바라봤을 때의 스카인라인 중 더 낮은 스카이라인까지만 각 건물들의 높이를 늘려야 문제가 제시한 스카이라인 제약을 그대로 유지할 수 있다 ) - 이처럼 행과 열을 다루는 문제는 먼저 문제 해결 방향을 설정하고, 그 방향에 맞게 행에 접근해야 할지, 열에 접근해야 할지를 헷갈리지 않도록 주의하자
