[Programmers] 요격 시스템 (Python, Java)

📖문제

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

✨핵심 내용 

A 나라 미사일: x 축에 평행한 직선 형태의 모양

B 나라 미사일: x 축에 수직 한 직선 형태의 모양, 발사된 미사일은 해당 x 좌표에 걸쳐 있는 모든 미사일 관통 가능
(단, 개구간이기에 s, e에서 발사하는 미사일로는 요격 불가, x가 실수인 곳에서 발사 가능)

🤔해결 아이디어 

유형: 그리디, 정렬

🟡 구조

1. targets을 e 기준으로 오름차순 정렬 

2. targets을 돌며 해당 인덱스[i]의 s가 저장된 인덱스[idx]의 e 보다 크거나 같은지 확인 

-> 이전에 등장한 e가 다음에 등장한 s 보다 작다면 둘은 겹치지 않는다 (아래 그림 참조) 

3. 조건을 만족한다면 idx를 현재 인덱스로 갱신하고, cnt += 1

---

✅정답 코드 (Python)

def solution(targets):
	# 1. [0] 기준 정렬
    targets.sort(key=lambda x: (x[1], x[0]))

	# 2. 한 번에 요격할 수 있는지 판단
    idx, cnt = 0, 1 # // 모두 한 번에 요격 가능하면 미사일의 최솟값은 1
    for i in range(1, len(targets)):
    	# 한 번에 요격 불가 (같은 x 상에 있지 않음)
        if targets[idx][1] <= targets[i][0]:
            cnt += 1
            idx = i

    return cnt

✅정답 코드 (Java)

package programmers.lv2;

public class 요격_시스템 {
    import java.util.*;

    class Solution {
        public int solution(int[][] targets) {
            // 1. [0] 기준 정렬
            Arrays.sort(targets, (o1, o2) -> (o1[1] - o2[1]));

            // 2. 한 번에 요격할 수 있는지 판단
            int idx = 0;
            int cnt = 1; // 모두 한 번에 요격 가능하면 미사일의 최솟값은 1

            for (int i = 1 ; i < targets.length; i++){
                // 한 번에 요격 불가 (같은 x 상에 있지 않음)
                if (targets[idx][1] <= targets[i][0]) {
                    idx = i;
                    cnt += 1;
                }
            }
            return cnt;
        }
    }
}