내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
단속카메라
ps:problems:programmers:42884
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 단속카메라 ====== ===== 풀이 ===== * 두 가지의 비슷하지만 조금 다른 그리디 풀이가 있다 * 첫번째 방법은, 진입점이 작은 구간부터 처리하는 방법이다. * 진입점 기준으로 구간들을 정렬하고, 순서대로 다음 처리를 해준다. 이전까지의 구간들의 겹치는 구간과 현재 구간과 겹치는 부분이 있다면, 겹치는 구간을 업데이트 해준다. 겹치지 않는다면, 이전까지의 겹치는 구간에 카메라를 설치한다. * 첨부된 코드는 이 방식이다. * 두번째 방법은, 진출점이 작은 구간부터 처리하는 방법이다. * 진출점이 작은 순서대로 구간들을 정렬하고 순서대로 처리를 한다. 현재 구간 안에 카메라가 설치되어 있는지 확인하고 (마지막으로 설치된 카메라가 현재 구간 안에 있는지 확인하면 된다), 설치되어 있지 않다면 현재 구간의 진출점에 카메라를 설치한다. * 이 방식으로 구현은 안해봤다. * 두 방법 모두 구간을 정렬한 뒤, 순서대로 읽으며 처리하는 것이라서 시간 복잡도는 O(nlogn)이다. 코드도 둘다 간단하다. ===== 코드 ===== <dkpr py> """Solution code for "Programmers 42884. 단속카메라". - Problem link: https://programmers.co.kr/learn/courses/30/lessons/42884 - Solution link: http://www.teferi.net/ps/problems/programmers/42884 """ INF = float('inf') def solution(routes): answer = 0 intersect_r = -INF for l, r in sorted(routes): if l <= intersect_r: intersect_r = min(r, intersect_r) else: answer += 1 intersect_r = r return answer </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_3}}
ps/problems/programmers/42884.txt
· 마지막으로 수정됨: 2021/07/05 10:09 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로