idx = 5일 때를 보자. idx = 5인 지점의 높이는 0이다. 이곳에 물이 쌓이기 위해서는 양 옆으로 0보다 큰 높이가 존재해야 한다.
여기서 물이 쌓이기 위한 조건이 결정됐다. 그건 바로 자신의 위치 양 옆 방향으로 자신보다 큰 높이가 존재해야 한다는 것이다.
그렇다면 양은 어떻게 결정이 될까?
자신을 기준으로 해서 좌우의 자신보다 높이가 높은 것 중 작은 것과 자신의 높이의 차이만큼 쌓이다.
어떻게, 얼마나 쌓이는지는 확인이 됐다.
양 끝점은 한쪽 벽이 없기에 어차피 물이 쌓이지 않는다. 그리고 양 쪽의 높이를 확인해야 하기 때문에 가장 높이가 높은 지점의 위치를 정해두면 두 지점 중 한 지점이 정해지니까 나머지의 파악이 쉬워진다.
class Solution {
public int trap(int[] height) {
int maxIdx = findMaxIdx(height);
int l = 0;
int r = height.length - 1;
int left = height[l];
int right = height[r];
int answer = 0;
// left to max
for (int i = 1; i < maxIdx; i++) {
left = Math.max(left, height[i - 1]);
if (left > height[i]) {
answer += left - height[i];
}
}
// right to max;
for (int i = r - 1; i > maxIdx; i--) {
right = Math.max(right, height[i + 1]);
if (right > height[i]) {
answer += right - height[i];
}
}
return answer;
}
private int findMaxIdx(int[] height) {
int maxHeight = 0;
int maxIdx = 0;
for (int i = 0; i < height.length; i++) {
if (maxHeight < height[i]) {
maxHeight = height[i];
maxIdx = i;
}
}
return maxIdx;
}
}
우선은 이렇게 풀었다. 그렇지만 반복문을 3번이나 순회하고 있다.
또한 배열의 길이가 0이나 1인 경우에 대한 대처가 부족하다.
class Solution {
public int trap(int[] height) {
// 엣지 케이스 처리
if (height == null || height.length <= 2) return 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
// 배열을 한 번만 순회하며 물의 양을 계산
while (left < right) {
if (height[left] < height[right]) {
// 왼쪽 벽이 더 낮은 경우
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
// 오른쪽 벽이 더 낮거나 같은 경우
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
}
이렇게 하면 한번의 반복을 수행한다.
또한 left, right 둘 중 최대 높이에 도달하면 나머지 한쪽만 계속 이동을 하면서 가둬진 물을 추가해 나간다.
N x N 크기의 격자 형태의 board가 존재하고 각 격자의 칸은 0 또는 1로 채워져 있으며, 0은 칸이 비어있음을 1은 해당 칸이 벽으로 채워져 있음을 나타낸다.
시작점은 (0,0) 칸(좌측 상단), 도착점은 (N-1, N-1)(우측 하단)이다.
직선 도로와 코너가 존재한다. 직선 도로는 상하 또는 좌우로 연결한 경주로를 의미하고 두 직선 도로가 직각으로 만다는 지점을 코너라고 한다.
직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 든다.
경주로를 건설하는데 들어가는 최소 비용은?
가중치가 존재하는 최단 거리 문제이다. 최소 비용을 구하기 위해서는 추가 금액이 들어가는 코너를 최소한으로 써야지 가능할 것 같다.
코너의 판정은 어떻게 해야 할까? 코너는 결국 이동 방향이 변경됐다는 것이다. 따라서 직전 이동 방향과 이번 이동 뱡향을 알면 코너인지를 판단할 수 있다. 즉 이전과 방향이 다르면 코너다.
좌우의 경우도 방향이 다르다. 하지만 이 경우는 코너가 아니다. 그런데 어차피 이 경우는 생각하지 않아도 된다. 최단거리를 찾는데 돌아가는 경우는 없다.
풀이를 생각해보자. 우선 가중치가 있는 최단거리를 구해야 하는 문제이다. 다익스트라로 풀 수 있을까?
다익스트라의 PriorityQueue에 넣을 때 방향도 함께 넣어서 방향별로 다른 경로로 판정하면 가능할 것 같다.
import java.util.*;
class Solution {
static class Node {
int r;
int c;
int dir;
int cost;
public Node(int r, int c, int dir, int cost) {
this.r = r;
this.c = c;
this.dir = dir;
this.cost = cost;
}
}
static final int INF = Integer.MAX_VALUE;
static int[] dr = {-1, 1, 0, 0}; //상하좌우
static int[] dc = {0, 0, -1, 1};
static int[][] distances;
public int solution(int[][] board) {
int N = board.length;
distances = new int[N][N];
for (int[] row : distances) {
Arrays.fill(row, INF);
}
distances[0][0] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
pq.add(new Node(0, 0, 1, 0));
pq.add(new Node(0, 0, 3, 0));
while(!pq.isEmpty()) {
Node curr = pq.poll();
int r = curr.r;
int c = curr.c;
int dir = curr.dir;
int cost = curr.cost;
if (distances[r][c] < cost) continue;
for (int d = 0; d < 4; d++) {
int weight = 100;
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (board[nr][nc] == 1) continue;
if (dir != d) {
weight += 500;
}
if (distances[nr][nc] > distances[r][c] + weight) {
distances[nr][nc] = distances[r][c] + weight;
pq.add(new Node(nr, nc, d, distances[nr][nc]));
}
}
}
int answer = distances[N-1][N-1];
return answer;
}
}
이렇게 풀었는데 오답이 됐다. 왜 틀렸는지 분석해 보자.
가장 큰 문제는 int [][] distances 배열이다.
나는 처음에는 직선으로 도착하거나 코너로 도착하거나 둘 중 하나이니까 그 두 경우를 전부 pq에 넣으면 어차피 저렴한 걸로 갱신되지 않을까 생각했다. 그런데 이렇게 풀게 되면 그 지점까지의 최솟값이 최종적인 최솟값이라고 보장이 돼야 한다. 하지만 이 문제는 그렇지 않다.
이렇게 관리하게 되면 같은 위치라도 다른 방향으로 도착했을 때의 비용 차이를 반영하지 못한다.
결과적으로, 특정 위치에 더 높은 비용으로 도착했지만, 방향이 달라서 이후 경로에서 더 낮은 총비용을 가질 수 있는 경우를 놓치게 되는 것이다.
이를 해결하기 위해 int [][][] distances로 3차원으로 방향까지 관리하도록 하겠다.
import java.util.*;
class Solution {
static class Node {
int r;
int c;
int dir;
int cost;
public Node(int r, int c, int dir, int cost) {
this.r = r;
this.c = c;
this.dir = dir;
this.cost = cost;
}
}
static final int INF = Integer.MAX_VALUE;
static int[] dr = {-1, 1, 0, 0}; //상하좌우
static int[] dc = {0, 0, -1, 1};
static int[][][] distances;
public int solution(int[][] board) {
int N = board.length;
distances = new int[4][N][N];
for (int d = 0; d < 4; d++) {
for (int[] row : distances[d]) {
Arrays.fill(row, INF);
}
}
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
for (int d = 0; d < 4; d++) {
distances[d][0][0] = 0;
pq.add(new Node(0, 0, d, 0));
}
while(!pq.isEmpty()) {
Node curr = pq.poll();
int r = curr.r;
int c = curr.c;
int dir = curr.dir;
int cost = curr.cost;
if (distances[dir][r][c] < cost) continue;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
int weight = 100;
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (board[nr][nc] == 1) continue;
if (dir != d) {
weight += 500;
}
if (distances[d][nr][nc] > distances[dir][r][c] + weight) {
distances[d][nr][nc] = distances[dir][r][c] + weight;
pq.add(new Node(nr, nc, d, distances[d][nr][nc]));
}
}
}
int answer = INF;
for (int d = 0; d < 4; d++) {
answer = Math.min(answer, distances[d][N-1][N-1]);
}
return answer;
}
}
각각의 아이들에는 rating이 할당 돼 있다. 이런 아이들에게 다음 조건에 따라 사탕을 줄 것이다.
각각 아이들은 최소한 하나의 사탕을 받아야만 합니다.
rating이 높은 아이는 인접한 아이보다 더 많은 사탕을 받습니다.
아이들에게 나눠줘야 하는 사탕의 최소 개수를 구하여라.
어차피 1개씩은 다 받아야 하니까 모든 아이에게 1개씩을 나눠주고 보자.
i 기준에서 i-1과 i+1의 값을 비교해야 한다. 양 옆의 값 중 자신보다 작은 값이 존재한다면 사탕을 양 옆보다 더 줘야 한다.
예시를 보겠다.
[1, 0, 2] 일 때 우선 가운데 1번 idx의 아이는 사탕을 1개만 받아도 된다.
0번 idx는 1번 idx보다 rating이 크므로 2개를 받아야 한다.
2번 idx는 1번 idx보다 rating이 크므로 2개를 받아야 한다.
양쪽 방향에서 중앙으로 접근해 가능 방식으로 푸는 게 좋을 것 같다.
왼쪽에서 오른쪽 방향으로 훑으면서 오른쪽 이웃과 비교
오른쪽에서 왼쪽 방향으로 훑으면서 왼쪽 이웃과 비교
그런데 이 두 결과를 어떻게 합쳐야 할까?
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
// left to right;
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// right to left;
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
// 이미 더 많다면 추가할 필요가 없다.
if (candies[i] > candies[i + 1]) continue;
candies[i] = candies[i + 1] + 1;
}
}
return Arrays.stream(candies).sum();
}
}
우선 왼쪽 → 오른쪽 방향으로 진행하면서 사탕을 분배한다.
그 후 오른쪽 → 왼쪽 방향으로 진행하면서 사탕을 조건에 따라 분배해야 하는데 만약 rating이 오른쪽보다 높은데도 이미 주어진 사탕이 오른쪽 사탕보다 많다면 더 이상 추가해 줄 필요가 없다.
그렇다면 자신을 제외한 왼쪽곱, 오른쪽곱의 배열을 만들어 두 배열의 값을 곱해서 반환하면 된다.
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] left = new int[nums.length];
Arrays.fill(left, 1);
int p = 1;
for (int i = 1; i < nums.length; i++) {
left[i] = p * nums[i - 1];
p *= nums[i - 1];
}
p = 1;
int[] right = new int[nums.length];
Arrays.fill(right, 1);
for (int i = nums.length - 2; i >= 0; i--) {
right[i] = p * nums[i + 1];
p *= nums[i + 1];
}
int[] answer = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
answer[i] = left[i] * right[i];
}
return answer;
}
}
그런데 위의 풀이를 보면 left, right, answer라는 추가 공간이 많이 사용됐다.
생각해 보면 그냥 answer 배열 하나에 다 처리를 해도 될 것 같다.
또한 배열을 1로 채워주고 있는데 시작 지점만 채워주면 된다.
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
answer[0] = 1;
for (int i = 1; i < n; i++) {
answer[i] = answer[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
answer[i] *= right;
right *= nums[i];
}
return answer;
}
}
