[Leetcode] 2280. Minimum Lines to Represent a Line Chart

https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart/description/

점 여러 개를 주고 그래프를 그렸을 때 직선이 몇 번 필요한 지 묻는 문제이다. 그래서 점을 정렬하고 순차적으로 기울기를 계산함으로써 기울기가 바뀌는 구간을 찾고자 했다. 그리고 실패했다.

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        stockPrices.sort()

        slop = []

        for i in range(1, len(stockPrices)):
            nSlop = (stockPrices[i][1] - stockPrices[i-1][1])/(stockPrices[i][0] - stockPrices[i-1][0])

            if not slop or slop[-1] != nSlop:
                slop.append(nSlop)

        return len(slop)
        

코드가 문제가 없을 줄 알았다. 그러나 파이썬의 자리수 계산에서 문제가 있었던 것 같다.

[[1,1],[500000000,499999999],[1000000000,999999998]]

에 대해서

499999998/499999999
0.999999998
499999999/500000000
0.999999998

라는 결과를 내었다. 자릿수가 너무 작아서 발생한 문제 같았다.

방법을 찾아보니

from decimal import Decimal, getcontext

python에는 decimal이라는 모듈이 있는데 이것을 통해서 정확한 자릿수를 지정할 수 있는 것 같다.

from decimal import Decimal, getcontext

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        getcontext().prec = 50
        
        stockPrices.sort()

        slop = []

        for i in range(1, len(stockPrices)):
            nSlop = Decimal(stockPrices[i][1] - stockPrices[i-1][1])/Decimal(stockPrices[i][0] - stockPrices[i-1][0])

            if not slop or slop[-1] != nSlop:
                slop.append(nSlop)

        return len(slop)
        

이렇게 하니까 풀렸는데 이게 맞는 방법인지는 잘 모르겠어서 다른 방법을 찾아봤다.

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:

        stockPrices.sort()

        if len(stockPrices) < 2:
            return 0
        
        dx = stockPrices[1][0] - stockPrices[0][0]
        dy = stockPrices[1][1] - stockPrices[0][1]

        slop = []
        answer = 1

        for i in range(2, len(stockPrices)):
            ndy = stockPrices[i][1] - stockPrices[i-1][1]
            ndx = stockPrices[i][0] - stockPrices[i-1][0]

            if dy * ndx != ndy * dx:
                answer += 1
                dy = ndy
                dx = ndx

        return answer
        

다른 분의 코드를 보니까 나눗셈을 하지 않고 곱셈으로 풀었다. dy/dx != ndy/ndx에서 통분을 해서 dy ndx != ndy dx로 함으로써 자릿수 문제를 해결했다. 나눗셈을 해야할 경우에 곱셈으로 돌릴 수 없을지 고민해볼 필요가 있겠다.