1. 가장 간단한 방법은 [-30,000, 30,000]의 좌표를 갖는 1차원 배열을 0으로 초기화해서 하나 만들고 각 routes의 진입 지점부터 진출 지점까지 +1 한다. 모든 routes에 대해서 이 작업을 수행하면 가장 큰 좌표부터 내림차순으로 차량이 단속용 카메라를 만날 수 있도록 카메라를 설치하는 것이다. 하지만 단순한 방법인만큼 비용이 많이 든다. 최악의 경우엔 크기가 60,000인 배열이 필요하다. 그리고 차량이 최대 10,000대이기 때문에 못해도 6억 번 정도의 연산이 필요하다. 따라서 이 방법은 시간이 많을 때나 도전할 수 있는 방법이다.
2. 그 다음은 routes를 순회하면서 새로운 차량의 동선을 만날 때마다 카메라를 설치하는 것이다. 그리고 카메라의 좌표를 설치 가능한 범위를 기억하고 있다가 그 범위를 사용해서 새로운 차량이 카메라에 보이는지 검사한다. 보인다면 범위를 수정해주고 보이지 않는다면 새로운 카메라를 설치한다. 이 방법은 최악의 경우엔 하나의 카메라에 하나의 자동차만 보이는 경우 약 1억 번 정도의 연산이 필요하다. 따라서 이 방법도 영 좋지 못한 것 같다. 그리고 차량이 들어오는 순서에 따라서 최적의 카메라 대수를 구하지 못할 수도 있다.
3. 마지막 방법으로 문제를 해결했다. 우선 routes를 진출 지점을 기준으로 오름차순 정렬한다. 그리고 가장 첫번째 동선부터 카메라를 마지막으로 카메라를 설치한 위치를 기억하면서 설치해나간다. 그리고 그 다음 자동차의 진출 지점이 카메라에 담기지 않는 경우엔 카메라를 하나 더 설치한다. 이 방법은 정렬에 O(nlogn)이 걸리고 문제를 해결하는 데에는 O(n)이므로 위의 경우보다 훨씬 좋은 복잡도를 보인다.
'PS > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 기지국 설치 (C++) (2) | 2022.10.06 |
|---|---|
| [프로그래머스] 숫자 게임 (2) | 2022.10.05 |
| [프로그래머스] 단어 변환 (0) | 2022.10.02 |
| [프로그래머스] 야근 지수 (2) | 2022.10.01 |
| [프로그래머스] 최고의 집합 (0) | 2022.10.01 |