여전히 PS재활훈련 중이다. 최근 계속 그리디만 풀고 있는 것 같다. 이 문제는 제한사항에서 볼 수 있듯이 입력되는 변수들의 크기가 꽤나 크다. 특히 N의 경우는 2억이나 되기 때문에 O(N^2)만 돼도 복잡도가 어마 무시하다. 따라서 못해도 O(N) 혹은 O(logN)에는 해결해야 하는 문제였다. 이게 이 문제에서 가장 큰 힌트였다고 생각한다. O(logN)은 트리나 이분 탐색이 아닌 이상은 구현하기가 쉽지 않다. 따라서 이 문제는 다른 방법들을 모두 제치고 선형 알고리즘일 것이라고 생각할 수 있다. 이 문제에서 얻을 수 있는 또 다른 힌트는 stations가 이미 오름차순으로 정렬되어 있다는 부분이다. 물론 그냥 문제가 친절하기 때문일 수도 있지만, 오름차순으로 정렬되어 있다는 말을 보면 괜히 낮은 ..
