[python] 프로그래머스 - 지형 편집

🤔문제 해결

Lv4 | 이분탐색 or 완전탐색(?)

 

이분탐색으로 코드를 구현했더니 효율성에서 실패했다.

그래서 한층한층 값을 저장하고 다음 층의 값을 구할 때는 이전에 저장한 층의 값을 이용하기로 했다.

 

먼저 2차원 행렬을 일렬로 세운고 오름차순 정렬한다. 

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

 

다음 제일 낮은 층( 여기서는 0 )으로 평평하게 만들 경우를 구한다.

지형을 빼는 작업만 하면 되므로 ( 전체지형 수 - 가장 낮은층의 지형 수 ) * Q(빼는 비용)

빨간 부분을 다 지우면 높이가 0인 평평한 지형을 만들 수 있다.

• 값은 21칸 * Q(지우는 값) = 63

이제 일렬로 세운 리스트를 하나하나 탐색한다. ( 맨앞은 했으니 0부터 )

리스트[1] 은 1이다. (1층으로 평평하게 한다는 뜻)

* 로 표시된 층이 생성 되어야 한다. 초록칸은 원래 없던곳이고, 빨간 칸은 원래 있던 곳이다.

0층으로 만드는 값(63)에 초록칸과 빨간칸을 더해줘야 한다.

하지만 초록칸은 새로 지형을 추가하는 것이고, 빨간칸은 기존에 지웠던 지형을 다시 복구하는 것이다.

새로 지형을 추가하려면 +P, 복구하는 것은 -Q의 값이 든다.( Q를 써서 지웠으니 Q를 써서 복구한다.)

• 0층 값 + 초록( (높이 차이)*(개수)*P ) - 빨강 ( (높이 차이)*(나머지 개수)*Q )
• 63 +5 - 24 = 44

다음은 리스트[2] = 2 이다.

두개의 초록 지형을 새로 추가하고, 기존에 지웠던 7개의 빨간 지형을 복구한다.

 

다음 리스트[3] = 2 이다. 이전에 진행한 2층과 똑같으므로 패스... 이런식으로 제일 고층까지 올라가면 해결!

 

💨 시간을 줄이는 팁은 밑에서 고층으로 갈 수록 비용이 줄어들고 어느 순간부터 다시 비용이 늘어난다.

즉 변곡점이 하나 있다. 그 부분에 멈추면 될듯하다( 이분탐색에서 그렇게 했음 )

 

💻소스 코드

 from itertools import chain


def solution(land, P, Q):
    # 일렬로 세우기
    line = list(chain.from_iterable(land))
    line.sort()
    # print(line)
    n = len(line)

    # 가장 낮은 층으로 편집 (무조건 0이 아니라 가지고 있는 층중에 맨 밑)
    # 가장 낮은 층은 지형이 다 있으므로 그 위의 블록을 모두 제거하면 된다.
    cost = (sum(line) - line[0] * n) * Q
    answer = cost

    # 한층씩 쌓기
    for i in range(1, n):
        if line[i] != line[i - 1]:
            # print(f'cost: {cost}, line[i-1]: {line[i - 1]}, line[i]: {line[i]} ')
            cost = cost + ((line[i] - line[i - 1]) * i * P) - ((line[i] - line[i - 1]) * (n - i) * Q)
            if answer < cost:  # 시간 단축 - 변곡점
                break
            answer = min(answer, cost)
    return answer

and 실패한 코드 💢 ( 이분 탐색 ) - 정확성은 맞으나 효율성 테스트 떨어짐

이분 탐색
from collections import defaultdict


def solution(land, P, Q):
    answer = 0
    n = len(land)

    line = defaultdict(int)
    for i in range(n):
        for j in range(n):
            line[land[i][j]] += 1

    # print(line)

    def cal(k):
        p, q = 0, 0
        # print(f'i: {k}')
        for key, value in line.items():
            if key > k:
                q += (key - k) * value
            elif key < k:
                p += (k - key) * value

        # print(f'total: {p * P + q * Q}')
        return p * P + q * Q

    bottom = min(line)
    top = max(line)
    while True:
        mid = (bottom + top) // 2

        up_val = cal(mid + 1)
        mid_val = cal(mid)
        down_val = cal(mid - 1)
        if mid_val <= up_val and mid_val <= down_val:
            answer = mid_val
            break
        elif down_val < mid_val:
            top = mid - 1
        elif up_val < mid_val:
            bottom = mid + 1

    return answer
    
    

 

📕문제 확인

출처: 프로그래머스

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

코딩테스트 연습 - 지형 편집

---

문제 설명

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

입출력 예 설명

입출력 예 #1

• 모든 땅의 높이를 1로 맞추는 데는 블록 4개를 제거해야 하므로 8의 비용이 듭니다.
• 모든 땅의 높이를 2로 맞추는 데는 블록 1개를 추가하고 블록 1개를 제거해야 하므로 5의 비용이 듭니다.
• 모든 땅의 높이를 3으로 맞추는 데는 블록 4개를 추가해야 하므로 12의 비용이 듭니다.

따라서 최소 비용은 5이므로 5를 return 합니다.

입출력 예 #2
문제의 예시와 같으며 최소 비용은 33입니다.