99클럽 코테 스터디 32일차 TIL - 2280 Minimum Lines to Represent a Line Chart
2280. Minimum Lines to Represent a Line Chart / c++ / Medium / 1시간+
문제 및 코드
#include<algorithm>
class Solution {
public:
int minimumLines(vector<vector<int>>& stockPrices) {
sort(stockPrices.begin(), stockPrices.end(), [](vector<int>& a, vector<int>& b)->bool
{
return a[0] < b[0];
});
if (stockPrices.size() < 3) return stockPrices.size() - 1;
int answer = 0;
long long deltaX = 0;
long long deltaY = 0;
for (int i = 0; i < stockPrices.size()-1; ++i)
{
long long currentDeltaX = stockPrices[i + 1][0] - stockPrices[i][0];
long long currentDeltaY = stockPrices[i + 1][1] - stockPrices[i][1];
if ((deltaX == 0 && deltaY == 0) || deltaX * currentDeltaY != currentDeltaX * deltaY)
{
answer++;
}
deltaX = currentDeltaX;
deltaY = currentDeltaY;
}
return answer;
}
};
접근 방식
정렬
- 그래프를 그릴 때 필요한 선의 갯수를 반환하는 문제였다.
- 1번 의미를 풀어보자면 두 정점이 주어졌을 때, deltaY / deltaX 로 기울기를 구한 뒤, 그 기울기가 이전 기울기보다 달라지면 새로운 선이 필요한 것이므로 answer++ 해주는 로직이었다.
- 풀다가 알게 된 사실이지만, stockPrices는 정렬되어 있지 않아서, x값을 기준으로 정렬해줬다. 그 후 순회하면서 각 선분의 기울기를 구하고, 이전 기울기와 다르다면 answer++을 해줬었다.
- 3번에서 또 문제가 발생했었는데, deltaY / deltaX로 기울기를 구할 때, 500000000 /499999999 같은 경우 기울기를 1로 인식해서 값이 틀리게 나왔다.
- 한참 고민하다가 부동소수의 계산은 큰 정수의 계산으로 치환하는 편이 결과가 정확하다는 점이 기억나서, deltaY / deltaX가 아닌 이전deltaX * 현재deltaY 가 현재deltaX * 이전deltaY와 같은지로 기울기의 변화를 측정했다. (분모가 다른 분수의 비교 연산)
- 해결
생각해 볼 점
- stockPrices가 정렬되어 있지 않은걸 간과한 것이 컸다. (당연히 x값을 기준으로 정렬되어 있을 것이라고 생각했는데, 다음부턴 항상 정렬을 먼저 신경써야겠다.)
- 정밀한 소수점 자리 비교는 차라리 큰 정수형 비교로 치환하는 편이 좋다는 것을 몸소 체험할 수 있는 문제였다. (항상 부동소수점으로 인한 비교 오류가 있다는 것을 은연 중에 알고는 있었는데, 이번 기회에 확실하게 경험하고 해결할 수 있었다.)
해시태그
#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL