일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- 프로그래머스
- java #자바
- 재귀
- PYTHON
- 백준 #파이썬 #알고리즘 #코딩테스트
- 백준 #알고리즘 #파이썬 #코딩테스트
- css #생활코딩 #웹
- 투포인터
- react #리액트 #동빈나 #나동빈 #유튜브강의
- css #웹 #생활코딩
- DFS
- 파이썬
- 다이나믹프로그래밍
- 코딩테스트
- 파이썬 #백준 #알고리즘 #코딩테스트
- Dijkstra
- 다익스트라
- 자바 #java
- 알고리즘
- java #자바 #나동빈
- java #자바 #생활코딩
- 백트랙킹
- dp
- 프로그래머스 #파이썬 #알고리즘 #코딩테스트
- 프로그래머스 #파이썬 #코딩테스트 #알고리즘
- react #리액트 #동빈나
- 파이썬 #알고리즘 #코딩테스트 #프로그래머스
- BFS
- 백준
- java #자바 #동빈나
Archives
- Today
- Total
커리까지
[프로그래머스] 단속 카메라 파이썬 본문
728x90
SMALL
문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
- 차량의 대수는 1대 이상 10,000대 이하입니다.
- routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
- 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
- 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
입출력 예
routes | return |
---|---|
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]] | 2 |
입출력 예 설명
-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
참고 답안
- 진출 시점을
오름차순
으로 정렬하여 카메라 위치를 계산한다.- 진출 시점으로 하는 것이 다음 구간의 차량 진입 시점과 비교할 수 있다.
- 오름차순으로 정렬하면
[-20, -15], [-18, -13], [-14, -5], [-5, -3]]
가 된다. - 그럼 처음에
-30001
과-20
을 비교한다. - 현재 카메라 위치에서는
-20
을 잡지 못하기에 카메라를 설치하고 카메라 위치를 진출 지점-15
로 변경한다. - 그 다음에는
-15
와-18
을 비교하는데 카메라 위치가-18
보다 커서 설치하지 않고 넘어간다. - 그 다음에는
-15
와-14
를 비교하는데-14
가 더 크기 때문에 카메라를 설치하고 다시 카메라 위치를 조정한다. - 마지막에
-5
와-5
를 비교한다. - 같기 때문에 카메라를 설치하지 않는다.
def solution(routes):
answer = 0
routes.sort(key=lambda x:x[1])
camera = -30001
for route in routes:
if camera < route[0]:
answer += 1
camera = route[1]
return answer
728x90
LIST
'알고리즘 > 풀이' 카테고리의 다른 글
[프로그래머스] 불량 사용자 파이썬 (0) | 2023.06.15 |
---|---|
[프로그래머스] 기지국 설치 파이썬 (0) | 2023.06.13 |
[프로그래머스] 숫자 게임 파이썬 (0) | 2023.06.08 |
[프로그래머스] 단어 변환 파이썬 (1) | 2023.06.07 |
[프로그래머스] 야근 지수 파이썬 (0) | 2023.06.06 |
Comments