[프로그래머스] LV.4 지형 편집

문제

XX 게임에서는 지형 편집 기능을 이용하여 플레이어가 직접 게임 속 지형을 수정할 수 있습니다. 이 게임에서는 1 x 1 x 1 크기의 정육면체 블록을 쌓아 게임 속 지형을 표현합니다. 이때, 블록이 공중에 떠 있거나, 블록 하나가 여러 개의 칸에 걸쳐 놓일 수는 없습니다. 따라서 지형을 편집하기 위해서는 각 칸의 제일 위에 블록 1개를 새로 추가하거나, 제일 위에 있는 블록 한 개를 삭제하는 방식으로 지형을 수정해야 합니다. 이때, 블록 한 개를 새로 추가하거나 삭제하기 위해서는 게임머니를 사용해야 하므로 몇 개의 블록을 추가하고 삭제할지 신중한 선택이 필요합니다.

이 게임을 즐기던 한 플레이어는 N x N 크기의 지역에 자신만의 별장을 만들고 싶어졌습니다. 이를 위해서는 울퉁불퉁한 지형의 모든 칸의 높이가 같아지도록 만들어야 합니다. 이때, 블록 한 개를 추가하려면 P의 비용이, 제거하려면 Q의 비용이 들게 됩니다.
다음은 블록 한 개를 추가할 때 5의 비용이, 제거할 때 3의 비용이 드는 경우, 3 x 3 넓이의 모든 칸의 블록 높이가 같아지도록 만드는 예시입니다.

위 그림과 같이 지형 블록이 놓여 있는 경우 모든 칸의 높이가 3으로 같아지도록 한다면 다음과 같은 모양이 됩니다.

이를 위해서는 3보다 높은 칸의 블록 2개를 제거하고, 3보다 낮은 칸에 총 8개의 블록을 추가해야 하며, 2 x 3 + 8 x 5 = 46의 비용이 들게 됩니다.

그러나 아래 그림과 같이 모든 칸의 높이가 2로 같아지도록 할 때는 6개의 블록을 제거하고, 3개의 블록을 추가하면 6 x 3 + 3 x 5 = 33의 비용이 들게 되며, 이때가 최소비용이 됩니다.

현재 지형의 상태를 나타내는 배열 land와 블록 한 개를 추가하는 데 필요한 비용 P, 블록 한 개를 제거하는 데 필요한 비용 Q가 매개변수로 주어질 때, 모든 칸에 쌓여있는 블록의 높이가 같아지도록 하는 데 필요한 비용의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한

• land는 N x N 크기의 2차원 배열이며, N의 범위는 1 ≤ N ≤ 300입니다.
• land의 각 원소는 각 칸에 놓여 있는 블록의 수를 나타내며, 0 이상 10억 이하의 정수입니다.
• 각 칸에 블록 하나를 추가하는 데는 P, 제거하는 데는 Q의 비용이 들며, P, Q의 범위는 1 ≤ P, Q ≤ 100인 자연수입니다.
  

입출력 예시

land	P	Q	result
[[1, 2], [2, 3]]	3	2	5
[[4, 4, 3], [3, 2, 2], [ 2, 1, 0 ]]	5	3	33

풀이

2018 Summer/Winter Coding 에서 출제된 문제이다. 복잡해 보이지만 생각을 달리하면 의외로 쉽게 풀 수 있는 문제다. 일단 제한 조건으로 주어지는 값의 크기가 매우 크기 때문에, 효율적인 방식으로 풀어야 한다는 생각을 떠올려야 한다. 하나씩 살펴보며 차근차근 풀어보도록 하자.

1) 기준이 되는 블록

일단 문제에서 요구하는 답은 모든 칸의 블록 높이가 같아지는 시점에서 필요한 블록 개수가 최소인 경우이다. 즉 기준이 되는 지점은 바로 블록의 높이 라는 것을 알 수 있다. 예를 들어 land가 [ [4,4,3], [3,2,2], [2,1,0] ]으로 구성되어 있을때 이는 3X3 크기의 격자에서 각 블록의 높이가 4,4,3, 3,2,2 그리고 2,1,0을 차지하고 있는 모양을 말한다. 즉 아래의 이미지와 동일한 모형이다.

이때 블록을 평탄화하기 위해 기준을 잡을 수 있는 높이의 범위는 0 - 4가 된다. 왜냐하면 가장 낮은 지점의 블록 높이가 0이고 반대로 가장 높은 지점의 블록 높이가 4이기 때문이다. 만약 가장 높은 지점을 기준으로 평탄화를 하게 되면 상향 평준화가 될 것이고, 반대의 경우엔 하향 평준화를 하는 것과 같은 모양새가 될 것이다. 이때 블록을 추가 또는 제거하게 될텐데 각 작업에 소요되는 비용은 매번 다르다. 때문에 우리는 몇 층의 블록 높이를 기준으로 잡느냐 에 따라 최소비용을 구할 수 있음을 알 수 있다.

2) 기준이 되는 층수

가장 단순하게는 가장 낮은 지점부터 높은 지점까지 순회하며, 각 층수에서의 소요비용을 일일이 계산하는 방법이 있을 수 있다. 그러나 문제 제한 조건을 보면 블록의 높이는 최대 10억임을 알 수 있다. 즉 최악의 경우 층수를 순회하는데만 O(10억)의 시간이 필요하고, 추가적으로 몇 개의 블록이 추가되고 제거되는지 계산하는 시간 또한 필요하기에 당연히 시간초과가 날 것이다.

블록의 범위에서 기준이 되는 층수를 선택하고 또한 이 범위 값이 10억이라는 큰 수이기 때문에 우리는 이분탐색 알고리즘을 떠올릴 수 있다. 물론 문제를 푸는 방식은 단 한 가지만 존재하는 것은 아니기 때문에 이분탐색으로 접근해도 원하는 답을 구할 수 있을 것이다. 그렇지만 이분탐색 말고 발상의 전환을 통해 문제를 풀어보자.

주어진 land 배열은 2차원 배열이다. 해당 배열의 각 행(= land[i])은 격자무늬에서 가로 한 줄을 의미할 것이다. 그런데 우리는 원하는 답을 구할 때 기준으로 삼는 것은 단순히 블록의 높이라는 것을 파악했다. 이때 블록의 높이는 모두 제각각 다르지만, 이들의 순서는 크게 상관이 없다. 왜냐하면 항상 높이를 기준으로 블록이 추가/제거되기 때문에 어떻게 배열이 되어있더라도 추가/제거되는 블록의 수는 동일 하기 때문이다.

예를 들어 문제에서 주어진 그림에 해당하는 land 배열의 값은 [ [4,4,3], [3,2,2], [2,1,0] ] 이다. 그러나 이 배열이 [ [3,4,4], [1,3,0], [2,2,2] ] 처럼 순서가 섞여서 전달된다고 하더라도 요구하는 정답은 달라지지 않을 것이다. 각 블록의 높이는 변함이 없기 때문에 결국 추가/제거되는 블록의 수는 동일하게 구할 수 있기 때문이다.

따라서 우리는 2차원 배열을 1차원 배열로 변환해도 상관없다. 그리고 이 1차원 배열을 이용해서 O(N)의 시간으로 문제를 풀 것이다. 1차원배열을 만드는 이유는 간단하다. 먼저 각 블록의 순서 배열이 문제 풀이에 영향을 주지 않기 때문에 조금 더 쉬운 관리를 위해 배열을 풀어주는 목적이 있고, 가장 중요한 건 정렬을 통해 간단하게 기준이 되는 층수를 산정할 수 있기 때문이다.

주어진 land 배열을 1차원배열로 변환 후 오름차순 정렬하면 다음과 같을 것이다.

• [ 0, 1, 2, 2, 2, 3, 3, 4, 4 ]

해당 배열은 오름차순으로 정렬되어 있기 때문에 앞에서부터 차례로 접근하면, 기준이 되는 층수를 가장 낮은 지점부터 차례로 높은 지점까지 하나씩 선택해서 진행할 수 있다. 이때 배열의 크기 N은 최대값이 300이고 이는 2차원배열로 주어지기 때문에 1차원배열로 변환하면 해당 배열의 최대 길이는 90000이 될 것이다. 따라서 우리는 최대 O(90000)의 시간 내에 주어진 모든 블록의 층수 하나하나를 기준으로 삼을 수 있다.

3) 추가 또는 제거할 블록의 개수

1차원배열로 변환하면 위에서 설명한 바와 같이 기준이 될 층수를 하나씩 산정할 수 있음은 이해할 수 있다. 그러나 1차원배열을 이용해서 기준이 될 층수를 정하더라도, 이때 제거 또는 추가되어야 할 블록의 개수를 구하는 과정이 별도로 필요한데 이 과정에서 또 내부에 반복문을 통해 구한다면 소요시간이 매우 늘어날 우려가 있다.

하지만 오름차순 되어 있는 블록의 높이를 이용한다면 내부에서 반복문 없이 정렬 순서의 특징을 이용해서 필요한 추가/제거 블록 개수를 쉽게 계산할 수 있다.

설명을 쉽게 하기 위해 1차원배열을 다음과 같이 그래프화 했다. 가로축은 배열 요소의 인덱스를 의미하고 세로축은 블록의 높이를 의미한다.

오름차순으로 차례대로 정렬되어 있기 때문에 가장 먼저 다음의 규칙을 적용할 수 있다. 같은 높이를 공유하고 있는 블록은 별도의 계산이 필요하지 않다. 왜냐하면 같은 높이를 가지고 있다면 결국 추가/제거되는 블록의 개수는 동일하기 때문이다. 따라서 현재 몇 번째 블록이 처리되는지에 대한 정보만 잘 기록해둔다면 같은 층의 블록은 모두 계산을 건너뛸 수 있다.

앞서 추가/제거 작업에 필요한 소요비용은 모두 다르다고 했다. 따라서 단순히 추가되는 블록의 개수가 더 많다고 해서 추가 작업의 비용이 더 높은 것이 아니다. 즉 우리는 추가되는 블록의 개수와 제거되는 블록의 개수를 각각 구해 이들의 합을 비교해야 한다. 따라서 1차원배열에서 각 블록을 순회할 때 두 가지 과정이 필요하다.

1. 추가될 블록의 개수를 계산
2. 제거될 블록의 개수를 계산

앞서 우리는 추가/제거되는 블록의 개수는 모두 블록의 높이를 기준으로 한다는 점을 살펴보았다. 0번째 블록부터 이를 적용해보자. 0번째 블록의 높이는 0이기 때문에, 이 높이를 기준으로 한다면 이후에 있는 블록들은 모두 제거되어야 할 것이다. X 표시는 제거된 블록을 의미한다. 따라서 총 21개의 블록이 제거되어야 함을 알 수 있다. 반면 추가는 불가능하다. 어떤 블록도 추가하는 것을 통해 높이 0을 맞출 수 없거니와 가장 첫 번째 블록의 높이는 가장 낮은 지점이기 때문에 이후에 나오는 모든 블록은 해당 높이와 같거나 높기 때문에 추가가 불가능하다.

인덱스와 서수의 차이로 용어가 섞이고 있는데, 이후로는 인덱스 0의 값을 첫 번째 블록 이라고 표현하겠다.

• 첫 번째 블록(인덱스 0) : 추가 - 0개 / 제거 - 21개

이번엔 두 번째 블록의 경우를 살펴보자. 두 번째 블록은 높이가 1이기 때문에 이번엔 기준이 되는 높이가 1이 됨을 알 수 있다. 해당 높이를 맞추기 위해서는 높이가 1 보다 작은 블록은 추가되어야 하고, 높은 블록은 제거되어야 할 것이다. 즉 현재 블록 이전에 위치한 블록은 추가, 이후에 위치한 블록은 제거되어야 한다. 이때 동일한 높이일 경우는 생략한다. 이를 그림으로 나타내면 아래와 같다. O는 새롭게 추가된 블록을 의미한다.

• 두 번째 블록(인덱스 1) : 추가 - 1개 / 제거 - 13개

이처럼 각 높이를 기준으로 계속 계산하면 우리는 다음의 결과를 쉽게 얻을 수 있다.

• 세 번째 ~ 다섯 번째 블록(인덱스 2 ~ 4) : 추가 - 3개 / 제거 - 6개

• 6번째 ~ 7번째(인덱스 5 ~ 6) : 추가 - 8개 / 제거 - 2개

• 8번째 ~ 9번째(인덱스 7 ~ 8) : 추가 - 15개 / 제거 - 0개

이때 추가비용에는 5, 제거비용엔 3이 소요되기 때문에 가장 최소비용이 소요되는 높이는 2(녹색)을 기준으로 했을때로 33이 정답이 된다. 따라서 우리는 추가되는 영역과 제거되는 영역의 개수만 구해주면 O(N)의 시간으로 정답을 구할 수 있다. 그렇다면 해당 영역을 구할 공식을 만들어보자.

4) 추가되는 블록 개수 산출 공식

먼저 추가되는 블록의 개수를 구하는 공식부터 만들어보자. 일단 제일 먼저 유의해야 할 점은 높이가 동일한 블록은 공식 적용없이 모두 건너뛴다는 점이다. 아래 공식은 모두 서로 높이가 다를 때 적용됨을 주의하자.

위 그림들을 잘 보면 블록은 항상 현재 블록 이전에 위치한 곳에서만 추가되고 있음을 볼 수 있다. 예를 들어 두 번째 블록(인덱스 1, 주황색)이 기준일 때는 첫 번째 블록(인덱스 0)에 높이의 차만큼의 블록이 추가되고 있음을 볼 수 있다. 또한 세 번째 블록(인덱스 2, 녹색)이 기준일 땐 높이 2를 맞추기 위해 이전에 있는 블록들이 역시 동일하게 높이의 차 만큼 추가되고 있는 것을 볼 수 있다.

그렇다면 우린 각 블록끼리의 높이의 차를 구해야 하는데, 이는 모든 블록끼리 높이가 다를 수 있기 때문에 결국 다시 일일이 개개의 블록에 접근하기 위해 반복문을 돌아야한다. 하지만 다르게 생각해보자. 현재 배열은 오름차순으로 정렬이 되어있다. 그리고 현재 블록 이전에 위치한 원소들은 모두 지금 블록의 높이보다 그 높이가 작은 블록들을 의미한다. 그리고 이들 블록에 해주어야 할 작업은 현재 블록 높이와 동일한 만큼의 블록을 추가 하는 것이다. 다시 아래 두 개의 그림을 살펴보자.

빨간선의 기준은 현재 블록의 높이가 녹색일 때와 회색일 때를 상정한 것이다. 즉 녹색 블록 이전에 위치한 모든 블록은 해당 높이를 맞추기 위해 높이 2까지 블록이 추가되어야 하는데, 결국 이는 현재 녹색 블록 현재 블록의 인덱스 * 높이 - 이전 블록의 개수 라는 것을 알 수 있다. 현재 블록의 인덱스가 2라는 것은 이전에 2개의 칸이 있다는 것이고, 높이 또한 2이기 때문에 총 4개의 칸이 채워질 수 있다. 그런데 이때 하나의 블록(주황색)은 이미 존재하기 때문에 이를 제외해 4 - 1 = 3개의 블록이 필요한 것이다.

이는 회색의 경우도 마찬가지이다. 회색 블록의 기준이 되는 인덱스는 5이고, 이는 이전에 5개의 블록이 존재한다는 것을 의미한다. 여기에 높이 3을 곱하고 이전 블록 개수를 제외 하는 것으로 추가 될 블록 개수를 쉽게 구할 수 있다.

이를 계산하기 위해서는 이전 블록의 개수를 계속 유지시켜야 한다. 현재 블록의 인덱스는 배열 인덱스로 접근이 가능하고, 해당 높이 역시 1차원배열에서 가져올 수 있으나 이전 블록의 개수는 계속 누적되는 값이기 때문이다. 때문에 반복문에서 하나의 반복이 끝날때마다 prev 라는 변수를 따로 두어 현재 블록의 개수를 누적시켜 이 값을 계속 관리하도록 하자.

이를 종합하면 현재 높이에서 추가되어야 할 블록의 개수를 구하는 공식은 아래와 같다.

• 현재 블록의 높이 x 현재 블록의 인덱스 - 이전 블록의 개수

5) 제거되는 블록 개수 산출 공식

마찬가지로 제거되는 블록을 구하는 공식을 구해보자. 위에서 그림들을 잘 보면 현재 기준이 되는 높이가 되는 블록 이후에 위치한 블록들은 모두 해당 높이를 제외하고 제거되는 것을 볼 수 있다. 예를 들어 두 번째 블록(인덱스 1, 주황색)의 높이는 1이고, 그 뒤에 위치한 모든 블록은 높이에 해당하는 1칸을 제외하고 모두 제거되었다.

또한 세 번째 블록(인덱스 2, 녹색)의 경우에도 마찬가지이다. 이를 똑같이 높이를 기준으로 빨간선을 긋게 되면 아래 그림과 같이 나타난다.

이 값은 어떻게 구할 수 있을까? 먼저 모든 블록의 개수를 계산해서 가지고 있는 변수 total이 있다고 가정해보자. total은 처음 그림에서 보이는 것과 같이 색을 가지고 있는 모든 블록의 개수일 것이다. 그렇다면 제거되는 블록을 의미하는 X의 개수를 구하는 것은 당연히 total - 색이 있는 블록의 개수가 될 것이므로 우리는 색이 있는 블록의 개수만 구해주면 된다.

먼저 우리는 위에서 매 반복이 끝날 때마다 이전 블록의 개수를 반영하는 prev 변수가 있음을 확인했다. 이 값은 당연히 total에서 제외시킬 수 있다. 이를 제외한 색이 있는 블록들의 개수는 현재 블록의 높이 x (변환한 1차원배열의 크기 - 현재 블록의 인덱스) 라는 것을 알 수 있다.

이를 종합하면 현재 높이에서 제거되어야 할 블록의 개수를 구하는 공식은 아래와 같다.

• 모든 블록들의 개수 - 이전 블록의 개수 - (1차원배열의 크기 - 현재 블록 인덱스)

필요한 모든 공식을 구했으므로 이를 바탕으로 코드를 구현해보자.

6) 구현

먼저 land 배열을 1차원배열로 변환 후 오름차순 정렬을 해주자. 그리고 변환된 1차원배열을 이용해서 모든 블록 개수의 합을 구해주자. 이 합은 제거할 블록의 개수를 구할 때 사용할 것이다.

const blocks = land.flat().sort((a, b) => a-b);
const total = blocks.reduce((a, b) => a+b);

다음은 반복문을 돌기 위한 초기값 세팅이 필요하다. 반복문에서 필요한 체크값은 다음과 같다.

1. 같은 높이면 건너뛰기 위해 이를 체크하기 위한 값 floor

   • 높이의 범위는 0부터 10억이기 때문에, 이와 겹치지 않는 어떤 값으로도 초기화가 가능하다. 여기서는 -1로 초기화 한다.

2. 이전 블록 개수를 저장하기 위한 값 prev

   • 초기 개수는 당연히 0개 이므로 0으로 초기화

3. 최소값을 구하기 위한 answer

   • 값이 더 작은 경우 갱신되어야 하므로 비교를 위해 Infinity로 초기화

let floor = -1;
let prev = 0;
let answer = Infinity;

이제 반복문을 돌기위한 모든 준비가 끝났다. 위에서 구한 공식을 이용해서 추가/제거되어야 할 블록 개수를 구해주고 소요비용을 적용해서 각 단계에서의 비용을 구해, 더 작은 값이 나올 경우 answer를 갱신시켜 주자.

for (let i = 0; i < blocks.length; i++) {
  // 같은 높이인 경우엔 연산없이 건너 뜀
  if (floor !== blocks[i]) {
    floor = blocks[i];
    // 추가될 블록 개수 = 높이x인덱스 - 이전 블록 수
    const willBeAddedCount = blocks[i]*i - prev;
    // 제거될 블록 개수 = 전체개수 - 이전 블록 수 - (현재 인덱스 이후 나머지 인덱스의 개수*높이)
    const willBeDeletedCount = total - prev - (blocks.length-i)*blocks[i];
    // 각 개수 x 각 소요비용
    const result = willBeAddedCount*P + willBeDeletedCount*Q;
    
    // 더 작을 시 갱신
    if (answer > result) answer = result;
  }
  
  // 이전 블록의 개수는 계속 누적
  // blocks[i]는 해당 블록의 높이이자 곧 개수를 의미
  prev += blocks[i];
}

return answer;

7) 전체코드

다른 사람들의 풀이를 보면 이분탐색을 이용해서 푸는 것도 많이 볼 수 있다. 때문에 해당 풀이에서는 다른 방식으로 푸는 법을 소개했다. 두 풀이는 답을 도출하는 것은 같겠지만 접근 방식이 다르다. 본 포스팅에서 소개하는 방식은 블록의 개수에 초점을 두고 있는 반면, 이분탐색은 블록의 높이에 초점을 둔다는 점이다. 이분탐색 풀이를 찾아보고 더 마음에 드는 풀이가 있다면 해당 풀이를 적용하면 되겠다. 주석을 제외한 전체 코드는 다음과 같다.

function solution (land, P, Q) {
  const blocks = land.flat().sort((a,b) => a-b);
  const total = blocks.reduce((a,b) => a+b);
  
  let floor = -1;
  let prev = 0;
  let answer = Infinity;
  
  for (let i = 0; i < blocks.length; i++) {
    if (floor !== blocks[i]) {
      floor = blocks[i];
      
      const willBeAddedCount = blocks[i]*i - prev;
      const willBeDeletedCount = total - prev - (blocks.length-i)*blocks[i];
      const result = willBeAddedCount*P + willBeDeletedCount*Q;
      
      if (answer > result) answer = result;
    }
    
    prev += blocks[i];
  }
  
  return answer;
}

출처

https://programmers.co.kr/learn/courses/30/lessons/12984