Lv.2 : 요격 시스템

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• x축에 평행한 미사일들의 시작과 끝 인덱스가 주어진다.
• 요격 하기 위해서 미사일들의 범위에 해당하는 곳을 선택해야하며 끝 인덱스에 걸칠 수는 없다.
• 요격에 필요한 미사일의 최소 수를 구한다.

🔸 문제 풀이 🔸

• 최소한의 요격 미사일 개수로 최대한 많은 수의 폭격 미사일을 요격해야 하므로 그리디 문제로 볼 수 있다.
• 포격 미사일의 범위가 겹치는 인덱스를 빠르게 알기 위해 끝 인덱스로 오름차순 정렬한다.
• 문제에서의 제한 사항으로 실수 좌표도 가능하며 끝 인덱스에 겹치면 안된다.
  • 이전 포격 미사일의 끝 인덱스가 다음 포격 미사일의 시작 인덱스보다 작거나 같으면 새로운 요격 미사일을 쏴야한다.

---

🔸 코드 🔸

import java.util.Arrays;

class Solution {
    public int solution(int[][] targets) {
        Arrays.sort(targets, (o1, o2) -> o1[1]-o2[1]);

        int beforeEnd = 0;
        int answer = 0;

        for (int i = 0; i < targets.length; i++) {
            if (beforeEnd <= targets[i][0]) {
                beforeEnd = targets[i][1];
                answer++;
            }
        }

        return answer;
    }
}

🔸 코드 해석 🔸

• 포격 미사일 정보를 담은 이차원 배열 targets를 끝 인덱스를 기준으로 오름차순 정렬한다.
• int 변수 beforeEnd에 이전 포격 미사일의 끝 인덱스를 저장한다.
• 요격 미사일의 개수를 answer에 저장해 카운트한다.
• targets의 길이만큼 계산을 반복한다.
  • 이전 포격 미사일의 끝 인덱스 beforeEnd보다 현재 미사일의 시작 인덱스가 크거나 같으면, 새로운 요격 미사일이 필요하다.
  • beforeEnd에 현재 미사일의 끝 인덱스를 저장하고, answer + 1한다.
• answer을 반환한다.

---

🔸 end 🔸

• 처음엔 정렬을 생각하지못하고, 모든 x좌표 인덱스를 배열 혹은 맵으로 저장해서 겹치는 포격 미사일 번호를 카운트하고, 최대값으로 겹치는 부분에서 요격 미사일을 쏘는 방식으로 풀이했다.
  • 포격 미사일이 최대 50만개, x좌표는 1억까지 가므로 시간초과나 메모리 초과가 나타났고, 틀리는 경우도 있었다.
  • 질의응답을 참고해서 정렬이 필요하다는 것을 알고 코드를 수정했다.
• 자료구조를 잘못 선택하긴 했지만, Map에 관련해서 최대값을 구하는데 stream을 이용해서 풀어보고자 GPT를 참고해 코드를 짰었는데, 적당히 연습이 된 것 같다.
  • FE개발에만 CSS나 JS 구현에서 GPT를 이용했는데, stream 관련해서도 GPT를 많이 참고해야겠다.