Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 문자열
- 완전탐색
- 백준
- CS
- 이분탐색
- Effective Java
- 알고리즘
- 시뮬레이션
- 위상정렬
- 프로그래머스
- 구현
- 스택
- 후니의 쉽게 쓴 시스코 네트워킹
- swea
- 동적계획법
- 수학
- mst
- 세그먼트 트리
- JUnit 5
- 투 포인터
- dfs
- 유니온 파인드
- Network
- BFS
- 에라토스테네스의 체
- 그리디
- 플로이드-와샬
- Kotlin
- 백트래킹
- java
Archives
반갑습니다!
[프로그래머스] 단속카메라 본문
풀이
그리디 알고리즘을 사용해서 풀 수 있다. 우선 routes
를 오름차순으로 정렬하면 진입지점이 가장 빠른 순서대로 정렬된다. 그 상태에서 첫 번째 차량을 기준으로 잡고 다음 차량부터 비교해준다. 다음 차량이 기준점보다 먼저 고속도로를 빠져나가면 기준점의 위치를 변경한다. 다음 차량의 진입 지점이 기준점보다 나중이라면 기존의 CCTV로는 해당 차량을 감시할 수 없기 때문에 CCTV 개수를 늘리고 해당 차량의 진입점을 기준으로 한다.
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> routes) {
int answer = 1;
sort(routes.begin(), routes.end());
int pos = routes[0][1];
for (int i = 1; i < routes.size(); i++) {
if (pos > routes[i][1])
pos = routes[i][1];
else if (pos < routes[i][0]) {
answer++;
pos = routes[i][1];
}
}
return answer;
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스] 3 x n 타일링 (0) | 2020.09.02 |
---|---|
[프로그래머스] 기둥과 보 설치 (0) | 2020.09.02 |
[백준] 11005 진법 변환 2 (0) | 2020.08.31 |
[프로그래머스] 행렬의 곱셈 (0) | 2020.08.31 |
[프로그래머스] 경주로 건설 (0) | 2020.07.07 |