[10주차_금요일] 요격 시스템

[yeahdy]

• 사이트 : 프로그래머스(PG)
• 문제: 요격 시스템
• 번호: 181188
• 레벨: 2

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

### 💡 풀이 아이디어

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ targets의 길이 ≤ 500,000
• 0 ≤ s < e ≤ 100,000,000
• 10^5, O(NlogN)이하

💡 풀이 아이디어

• 최소한의 요격을 위해선, 끝자리를 기준으로 요격하기
  • e가 작은 순으로 오름차순 정렬
  • 초기값
    • cnt: 1
    • pos: 제일 처음 폭격의 끝지점
  • 현재 타겟의 시작값 < pos: pos로 요격한것 (continue)
  • 현재 타겟의 시작값 >= pos: pos로 요격 불가, pos값 현재 타켓의 e값으로 업데이트 및 cnt++

  Arrays.sort(targets, ((o1, o2) -> o1[1] - o2[1]));

    int cnt = 1;
    int pos = targets[0][1];
    for (int[] t : targets) {
        if (t[0] < pos) continue;
        pos = t[1];
        cnt++;
    }
    return cnt;

[yeongleej]

🤔 시간복잡도 고려사항

• targets의 길이 <= 500,000

=> 최대 O(NlogN)까지 가능

💡 풀이 아이디어

• bound : 요격 기준점

1. 시작점 기준으로 정렬하기

• s >= bound : 새로운 요격 기준점을 발견해야 함 + 해당 미사일의 끝점으로 요격 기준점 변경

• s < bound : 현재 요격 기준점에서 해당 미사일을 없앨 수 있지만, 현재 bound에서 가능한 모든 범위의 미사일을 없애야 하므로 미사일의 끝점이 가장 작은 값으로 요격 기준점을 설정해야 함

  • 즉, bound = min(bound, e) 필요

    
    for(int i=0; i<N; i++) {
    int s = targets[i][0];
    int e = targets[i][1];

  if(s >= bound) { answer++; bound = e; } else { bound = Math.min(bound, e);
  } }

2. 끝점 기준으로 정렬하기

• s >= bound : 새로운 요격 기준점을 발견해야 함 + 미사일은 끝점 기준으로 정렬되어 있으므로 해당 미사일의 끝점으로 요격 기준점을 변경해야 함
• s < bound : 현재 요격 기준점에 포함되고, 끝점도 요격 기준점보다 작지 않으므로 현재 요격으로 없앨 수 있음

  for(int[] t: targets) {
  if(t[0] >= bound) {
      answer++;
      bound = t[1];
  }
  }

처음에는 진입점 기준으로 정렬했는데 단속카메라 문제 풀어보깐 같은 문제더라고요! 문제를 좀 더 그리디적으로 생각해서 해결할 수 있는지 공부해야겠습니다 ㅠㅠㅠ

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ targets의 길이 ≤ 500,000 → 5 x 10^5이므로 O(N logN)이하로 해결

💡 풀이 아이디어

• 한번 쏠 때 가장 많은 미사일을 맞춰야 함 → 그리디한 방식으로 접근
• 어느 순간이 가장 효율적인가 ? → 미사일을 마지막 좌표에서 요격하기
• 타겟들의 좌표를 마지막 좌표를 기준으로 오름차순으로 정렬
• 요격 미사일의 좌표를 이용하여 타겟을 요격할 수 있는지 확인
• 요격할 수 없었을 때는 해당 미사일의 마지막 좌표로 요격 미사일 좌표 이동

  int missile = 0; // 요격 미사일의 좌표
  for (int i = 0; i < targets.length; i++) {
  // 개구간이기 때문에 등호
  // 해당 요격 미사일로 요격할 수 있는지
  if (missile <= targets[i][0]) {
      // 요격할 수 없었다면
      answer++;
      // 가장 늦게 격추하는 것이 효율적이므로 마지막 값으로 갱신
      missile = targets[i][1];
  }
  }

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= target(n) <= 500,000
• 0 <= s < e <= 100,000,000
• 최대 nLogn

💡 풀이 아이디어

• 끝점을 기준으로 한 우선순위 큐에 요격 미사일 넣어주기
• 요격 가능한 미사일(missle)의 가장 오른쪽 위치를 Integer.MAX_VALUE로 선언
• 큐가 빌 때까지 missle 위치와 폭격 미사일 원소의 시작점 비교하기
  • missle의 위치보다 폭격 미사일의 시작점의 위치가 크거나 같다면 요격 미사일 하나 설치하고, 요격 미사일의 위치를 폭격 미사일의 끝 위치로 바꿔주기

처음엔 이분탐색으로 풀리는 문제인 줄 알고, 어떻게 접근해야되는지 계속 고민을 하다가 정확한 미사일의 위치를 정할 수 없다는 걸 알고 아 아니구나,, 생각했습니다!

[icegosimperson]

🤔 시간복잡도 고려사항

• targets <=500,000 : O(N logN) 이하로 풀기

💡 풀이 아이디어

• 구하는 것 : 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값

• 내가 B나라 국민인데 미사일 최소한으로 쏘려면 어떻게 해야될까? - 그리디

• 최선의 선택 : 종료 지점에 맞춰서 쏘기 -> e구간 기준 정렬

  Arrays.sort(targets, (a, b) -> Integer.compare(a[1], b[1])); // e구간 기준 정렬

• 개구간은 범위에 포함되지 않기에 임의로e-0.5

  if(endShoot<s){ // 마지막 발사 위치보다 현재 시작 구간이 더 크면
  cnt++; // 새로운 미사일 설치
  endShoot = e-0.5; // 개구간 = 범위 포함X : 임의로 실수를 빼줌
  }

  

처음에 문제 어려워서 단속 카메라 먼저 풀고 왔는데 동일하게 푸는 문제였군요!

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 그리디
• 시간복잡도: 1 ≤ targets의 길이 ≤ 500,000 > O(N) + 정렬 O(logN) = O(NlogN)

💡 풀이 아이디어

• 가능한 많이 요격하기!! 개구간 시작점 기준으로 오름차순 정렬 후 시작점과 끝점이 넓으면 간격만큼 많이 요격할 수 있음
• 미사일 설치하기
  • 특정 개구간의 시작점이 현재 미사일 위치보다 크거나 같다
  • 해당 개구간의 끝점으로 이동
• 미사일 패스하기
  • 현재 미사일의 위치가 특정 개구간의 시작점보다 작다
  • 해당 개구간의 끝점과 현재 미사일의 위치 중 더 작은 위치로 이동 더 작은 위치로 갔을 때 더 많은 수를 요격할 수 있음. (+만약 해당 개구간의 끝점으로 바로 이동하면 끝점 - 끝점 사이에 시작점이 있을 경우 요격이 불가함)

이전에 풀었던 흙길 보수하기 문제랑 풀이 방식이 비슷한것 같아요! 처음에 이분탐색으로 접근했는데, 요격미사일을 최적의 장소에 여러 개를 둬야하는데 매번 판별할 수 있는 기준이 없다고 생각했어요