[10주차_금요일] 단속카메라

[yeahdy]

• 사이트 : 프로그래머스(PG)
• 문제: 단속카메라
• 번호: 42884
• 레벨: 3

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[baexxbin]

🤔 시간복잡도 고려사항

• 1 <= 차량의 대수 <= 10,000
• -30,000 <= 차량의 진입 지점, 진출 지점 <= 30,000
• 정렬 후 비교로 O(N)으로 풀이

💡 풀이 아이디어

• 이전 요격 시스템과 동일한 문제
  1. 끝지점을 기준으로 정렬
  2. pos를 두고 현재 차량의 진입점이 pos보다 크면 업데이트
• 요격 시스템과 다른점은, 이 문제는 시작과 끝 지점도 체크가능하므로 조건에 =이 포함 됨

[yeongleej]

🤔 시간복잡도 고려사항

• 차량 수 <= 10,000
• -30,000 <= 진입점, 진출점 <= 30,000

=> 완전탐색은 6억이므로 불가 => O(NlogN) or O(N)으로 생각해보기

💡 풀이 아이디어

• 진출점 기준으로 정렬
• last: 단속카메라 설치 기준점
• 차량의 진입점 > last 이면 단속카메라 새로 설치 필요

요격 시스템과 같은 문제이고, 한 차량의 진입점과 단속카메라 설치지점이 일치해도 가능하다는 점만 다른 것 같습니다

[Jewan1120]

🤔 시간복잡도 고려사항

• 차량의 대수는 1대 이상 10,000대 이하 → 따로 신경쓰지 않음

💡 풀이 아이디어

• 이전 문제와 동일
• 그리디한 방식으로 카메라를 설치하려면 마지막 좌표에 카메라를 설치하는 것이 효율적
• 따라서 자동차 구간의 마지막 값으로 오름차순 정렬
• 마지막 위치로 카메라 설치를 갱신하면서 처리할 수 있는 자동차 처리
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주이므로 등호는 필요 없음

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 차량의 개수(n) <= 10,000
• -30,000 <= 차량의 진입, 진출 지점 <= 30,000
• 60,000log60,000 까지 가능

💡 풀이 아이디어

• 진출 지점을 기준으로 한 우선순위 큐에 경로 넣어주기
• 설치 가능한 카메라의 위치를 Integer.MAX_VALUE로 선언
• 큐가 빌 때까지 카메라의 위치와 차량의 진입 지점 비교
  • 카메라의 위치보다 진입 지점이 크다면 카메라 설치하기

[icegosimperson]

🤔 시간복잡도 고려사항

N<=10,000, |진입, 진출 지점| <=30,000

💡 풀이 아이디어

• 단속 카메라를 어떻게 해야 효율적으로 설치할 수 있을까? - 그리디
  • 최선의 선택 : 진출 지점에 설치!
• 진출 지점 기준 정렬

  Arrays.sort(routes, (a,b) -> Integer.compare(a[1], b[1])); // 나간 지점 기준 정렬

• 설치 가능한 카메라가 없다면 (진입 지점 이전에 카메라 없으면)

• 진출 지점에 카메라 설치

      // 단속카메라 탐색 
      int cnt = 0; // 카메라 개수
      int endCamera= Integer.MIN_VALUE; // 처음엔 카메라 설치X
  
      for(int i=0; i<routes.length; i++){
          int s = routes[i][0]; // 진입 지점
          int e = routes[i][1]; // 진출 지점(나감)
  
          if(endCamera<s){ // 설치되지 않은 지점
              cnt++; // 카메라 설치
              endCamera = e; // 나가는 지점에 카메라 설치!
          }
      }

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 그리디
• 시간복잡도: 차량의 대수는 1대 이상 10,000대 이하 O(N) + 정렬 (OlogN) > O(NlogN)

💡 풀이 아이디어

1. 자동차를 가장 많이 찍기 위해선 출발점 기준으로 오름차순 정렬 후 진출 지점 부터 단속카메라 시작
2. 단속카메라 설치하기 현재 단속 시점과 다음 진입지점을 비교해서 더 클 경우 더 이상 해당 자동차는 찍을 수 없기 때문에 갱신
3. 단속카메라 유지하기 차량의 진입/진출 지점에 카메라가 있거나, 현재 단속 시점보다 작은 경우

   for(int i=1; i<routes.length; i++){
        if(current < routes[i][0]){
           answer++;
           current = routes[i][1];
        }else{  //current >= routes[i][0]
           current = Math.min(current, routes[i][1]);
        }         
   }