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

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

프로그래머스

🤔 문제분석

처음 문제를 접근할때 블록의 높이가 10억임을 보고 이분탐색으로 문제를 접근하려고 하였다.

아래의 두가지 조건을 세우고, 이분탐색을 해보았다.

1. 높이를 낮추면 P의 가중치의 합의 값은 변하지 않는다.
2. 높이를 높이면 Q의 가중치의 합의 값은 변하지 않는다.

만약 P와 Q의 가중치 합이 같다면(?) 이라는 조건을 찾아 해매다가 결국 문제를 해결하지 못하였다.

높이에 너무 집중한 나머지 정육면체 배열을 기준으로 최대값 최소값을 선정하고 그 배열을 순회하면서 최적화 값을 찾는것이 이 문제의 핵심포인트인데… 찾지 못하였다 😢

정육면체를 1차원 배열로 나타낸다면 300 * 300 = 90000 의 배열만 딱 한번 순회하면 문제를 해결 할 수 있다.

1. 높이의 최소값을 찾아서 Q 가중치로 가질 수 있는 최대값을 처음에 찾는다. 즉 높이가 가장 낮은 정육면체를 기준으로 가장 낮다면 P의 값은 0이 됨으로 Q의 가중치만 생각하여 계산한다.
2. 배열을 순회하면서 높이가 달라질때마다 P의 가중치를 증가시키고 Q의 가중치를 감소시킨다.

또한 배열을 증가시키면서 변곡점이 존재하게 되는데 cost값이 내려가다가 어느순간 올라가는 지점이 존재한다.

아래의 이분탐색으로 최소값을 찾는 과정을 설명해준다.

💻 코드

• chain을 활용 하였는데 from_iterable은 N차원 배열을 N-1 차원 배열로 flat하게 만들어준다.

from itertools import chain

def solution(land, P, Q):
    land = list(chain.from_iterable(land))
    land.sort()
    n = len(land)

    # Q의 맥스값부터 시작해서 높이가 달라질때마다 값을 갱신한다.
    cost = sum([land[i] - land[0] for i in range(1, n)]) * Q
    answer = cost

    for i in range(1, n):
        # 높이가 달라진다면 이제 P가중치를 증가, Q가중치를 감소시킨다.
        if land[i] != land[i-1]:
            h = land[i] - land[i-1]
            cost += h*(i*P) - h*(n-i)*Q
            answer = min(cost, answer)

    return answer

이분탐색 풀이 (번외)

import sys
from collections import defaultdict

def solution(land, P, Q):
    n = len(land)
    height = defaultdict(int)
    for i in range(n):
        for j in range(n):
            height[land[i][j]] += 1

    def cal(h):
        p_cnt = 0
        q_cnt = 0

        for key in height.keys():
            if h > key:
                p_cnt += (h - key) * height[key]
            elif h < key:
                q_cnt += (key - h) * height[key]

        return p_cnt * P + q_cnt * Q

    start = 0
    end = max(height)
    answer = sys.maxsize
    while True:
        mid = (start + end) // 2

        d_value = cal(mid-1)
        m_value = cal(mid)
        u_value = cal(mid+1)

        if m_value <= d_value and m_value <= u_value:
            answer = min(answer, m_value)
            break
        elif d_value < m_value:
            end = mid - 1
        elif u_value < m_value:
            start = mid + 1

    return answer