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
- 코딩테스트
- 백준
- BaekJoon
- c++
- Algorithm
- 보석쇼핑
- 투포인터
- 서버개발캠프
- 삼성 #코테 #2020상반기 #c++
- IBK기업은행 #기업은행 #디지털 #직무 #정리
- 유니온파인드
- Union-find
- 식단
- 코테
- Smilegate
- LIS #Algorithm #요소추적
- BFS
- 소감
- 스마일게이트
- 중반부
- 1편
- 카카오
- 카카오인턴
- 알고리즘
Archives
- Today
- Total
짱아의 개발 기록장
프로그래머스. 단속카메라(c++) / 그리디(Greedy) 본문
반응형
이 문제는 도저히 아이디어가 생각나지 않아 코드는 참고하지 않고 아이디어만 다른 분의 아이디어를 참고해서 풀었다.
아래가 다른 분의 아이디어이다.
[메인 로직]
첫 번째 카메라는 첫 번째로 차가 빠져나가는 지점에 설치해야 합니다. 왜냐하면 이 지점에서 설치하지 않으면 첫 번째로 빠져나가는 차는 찍을 수 없기 때문입니다. 그 지점에 카메라를 설치하면 해당 지점을 지나는 차들은 모두 카메라에 찍히게 되므로 더 이상 신경 쓸 필요가 없습니다.
두 번째 카메라는 아직 카메라에 찍히지 않은 차 중에서 첫 번째로 차가 빠져나가는 지점에 설치하면 됩니다. 두 번째 지점에 카메라를 설치하면 해당 지점을 지나는 차량들은 모두 찍히게 되므로 더 이상 신경 쓸 필요가 없습니다.
이런 식으로 계속 해서 카메라를 설치하는 과정을 거치면 됩니다. 요점은, 카메라가 설치 되었을 때, 더 이상 신경쓰지 않아도 되는 차량들을 확실하게 고려하지 않는 방식으로 프로그래밍을 해야 한다는 것입니다.
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
32
33
34
|
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int solution(vector<vector<int>> routes) {
int answer = 0;
vector<vector<int>> v;
int check[10001] = {0, };
for(int i=0; i<routes.size(); i++){
vector<int> temp;
temp.push_back(routes[i][1]);
temp.push_back(routes[i][0]);
v.push_back(temp);
}
sort(v.begin(), v.end());
for(int i=0; i<v.size(); i++){
if(check[i]) continue;
int num = v[i][0];
answer++;
for(int j=0; j<v.size(); j++){
if(v[j][1]<=num && num<=v[j][0]){
check[j] = 1;
}
}
}
return answer;
}
|
cs |
반응형
'Algorithm > Programmers' 카테고리의 다른 글
프로그래머스. 디스크컨트롤러(c++) / 힙(Heap) (0) | 2021.01.08 |
---|---|
프로그래머스. 카펫(c++) / 완탐(Brute Force) (0) | 2021.01.08 |
프로그래머스. 다리를 지나는 트럭(c++) / 큐(queue) (0) | 2021.01.07 |
프로그래머스. 지형 이동(c++) / bfs+MST(kruskal) (0) | 2020.08.28 |
프로그래머스. 징검다리(c++) / 이분탐색 (0) | 2020.08.28 |
Comments