[프로그래머스] 기지국 설치 (C++)

---

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

 

이 문제에서 얻을 수 있는 또 다른 힌트는 stations가 이미 오름차순으로 정렬되어 있다는 부분이다. 물론 그냥 문제가 친절하기 때문일 수도 있지만, 오름차순으로 정렬되어 있다는 말을 보면 괜히 낮은 숫자부터 시작하고 싶다. 나는 이쯤에서 문제를 어떻게 풀어야 할지 실마리를 잡게 됐다.

 

하나의 기지국의 담당하는 부분은 [낮은 좌표, 높은 좌표]로 표현할 수 있다. 현재 좌표보다 낮은 좌표들은 모두 기지국이 적절하게 설치되어 있다고 가정한다면 [현재 위치, 낮은 좌표]가 추가로 기지국을 설치해서 커버해야 하는 범위다. 그리고 하나의 기지국을 가장 베스트 하게 설치했을 때 하나의 기지국은 (2w+1)만큼의 범위를 담당할 수 있다. 따라서 (커버해야 하는 범위 / 2w+1)를 구하고 올림을 하게 되면 최소로 필요한 기지국의 개수를 구할 수 있다. 

 

대신 문제를 풀 때 예외 조건이 몇 가지 있을 수 있다. 처음부터 모든 경우를 엄밀히 생각하고 코드를 작성하면 예외 사항이라고 하기는 뭐하지만, 나 같은 경우엔 현재 좌표, 기지국 범위 등의 숫자를 정할 때 정확한 룰을 세우지 않고 시작해서 오류가 났었다. 예를 들면, 현재 좌표를 기지국이 설치되어서 문제없는 곳까지 할 것인가 아니면 그것보다 +1 된 지점으로 할 것인가 등이 있다.

 

나눗셈 + 올림을 구현하는 부분을 좀 더 아름답게 짤 수도 있을 것 같다. 이 정도면 나쁘지 않다고 생각은 되지만 보통 이런 연산을 한 줄로 처리하는 게 멋있다.

 

---

문제를 보고 든 생각을 평소보다 좀 더 세심하게 적었는데 이렇게 머릿속의 로직을 말로 풀어 설명하면 나도 좀 더 내 로직에 대해 정확히 이해할 수 있게 되는 것 같다. 하지만 글로 적는 게 아니라 실제로 말로 하게 되면 말보다 생각이 먼저 나가면서 꼬이는 경우가 많다. 말 조리 있게 잘 하는 사람들 보면 신기하다.