오늘의 문제는 [ith day, ith price]의 원소를 갖는 stockPrices라는 리스트가 주어졌을 때, 이를 2d 그래프로 그리면 몇 개의 line으로 그래프를 그릴 수 있는지 파악하는 것이다. 나는 문제를 수학적으로 접근하고자 했으며, 이에 각 구간별 기울기를 파악하고자 했다. 1) 초기에는 y = ax + b라는 직선을 구하려 했으나 동일한 day에 여러 개의 price를 가질 수 없으므로 기울기만 구해도 충분하다는 것을 파악했다. 2) 다음으로 기준 값을 최대한 덜 갱신하기 위해 기울기가 변할 때만 기준 값을 갱신하였으나 오류가 발생하였다. 이는 기준 값을 반복적으로 갱신하지 않으면, 다음 기울기와 비교할 때 문제가 발생하기 때문이다. 3) 마지막으로 알고리즘은 완벽했으나, 파이썬 부동 소수점 오차 문제에서 에러가 발생하였다. 이에 fractions 모듈을 활용하였다.
구체적인 문제 풀이는 다음과 같다.
stockPrices의 원소 갯수가 1개라면, 선분이 필요 없으므로 바로 return 0 한다.
stockPrices를 정렬한다. ⇒ 차례대로 기울기를 파악하기 위함.
stockPrices의 첫 번째와 두 번째 값을 활용해 초기 기울기를 구한다. ⇒ Fraction((end_val - start_val), (end_day - start_day))
start_day, start_val을 end_day, end_val로 갱신한다.
초기 answer = 1로 세팅한다.
반복문을 통해 3번째 원소부터 조회하며 각 값을 end_day와 end_val로 설정하여, 이전 값인 start_day와 start_val을 활용해 기울기를 구한다.
만약 해당 기울기가 이전 기울기가 다르다면, 기준 기울기를 갱신하고, answer += 1 한다.
start_day와 start_val을 end_day와 end_val로 갱신한다.
파이썬을 비롯한 많은 언어에서 부동 소수점 방식을 채택할 때 많은 오류가 발생한다.