[Java] 프로그래머스 : 요격 시스템

🤔 문제

🔗

각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

💡 풀이과정

특정 범위에 있는 폭격 미사일을 요격하는 미사일의 개수를 나타내는 문제이다.

구조를 그림으로 나타내면 다음과 같다.

폭격 미사일 배열을 순회해 기존에 있는 요격 미사일로 폭격 가능한지 따지는 방법으로 풀 수 있다.

폭격 가능할 경우 필요에 따라 요격 미사일의 요격 범위 (s, e)를 수정해준다.

폭격 불가능할 경우 새로운 요격 미사일을 추가하는 방식으로 풀면 된다.

 

하지만 폭격 미사일 배열을 그대로 사용하면, s 좌표와 e 좌표를 모두 고려해주어야 하므로 복잡하다.

그렇다면 배열을 정렬해주면 어떨까?

배열을 뒤쪽에 맞추어 정렬해보자.

폭격 미사일의 e 좌표는 반드시 직전 미사일을 폭격한 요격 미사일의 e 좌표보다 작을 수밖에 없다.

따라서 s 좌표만을 고려해 문제를 풀면 된다.

 

미사일의 좌표 정보를 저장할 Target 클래스를 만들고 Comparable<T>을 구현해 정렬기준을 만들어주었다.

class Target implements Comparable<Target> {
    int x1;
    int x2;
    
    public Target(int x1, int x2) {
        this.x1 = x1;
        this.x2 = x2;
    }
    @Override
    public int compareTo(Target t) {
        if(this.x2==t.x2) return t.x1-this.x1;
        else return t.x2-this.x2;
    }
}​

x1은 범위의 s 좌표, x2는 e 좌표이다.

x2가 같을 경우 x1을 비교해 범위가 더 넓은 폭격 미사일을 앞쪽에 배치해준다.

 

이제 미사일에 대한 Target 인스턴스를 생성하고 ArrayList에 담아 정렬한다.

ArrayList<Target> targetList = new ArrayList();
for(int[] t : targets) {
    Target target = new Target(t[0], t[1]);
    targetList.add(target);
}
Collections.sort(targetList);

 

x1은 요격 미사일의 e 좌표를 나타내는 변수이다.

폭격 미사일의 범위가 좌표 범위가 0≤s<e≤100,000,000이므로, x1을 100,000,000으로 설정해주었다.

answer은 요격 미사일의 개수를 나타내는 변수이다.

int x1 = 100000000;
int answer = 0;

 

이제 폭격 미사일 리스트를 순회하여 필요한 요격 미사일 개수를 계산한다.

고려해야 할 사항은 다음과 같다.

  1. 기존 요격 미사일로 타격 가능한 경우
    폭격 미사일의 e 좌표가 새로운 x1이 된다.
  2. 기존 요격 미사일로 타격 불가능한 경우
    새로운 요격 미사일을 추가하고, e 좌표를 x1으로 설정한다.
int x1 = 100000000;
for(int j=0 ; j<targetList.size() ; j++) {
    Target t = targetList.get(j);
	
    // 폭격 미사일의 s 좌표가 요격 미사일의 s 좌표보다 크면, 기존 미사일로 타격 가능하다.
    if(t.x1>x1) {
        x1 = t.x1;
    // 폭격 미사일의 e 좌표가 요격 미사일의 s 좌표보다 크면, 기존 미사일로 타격 불가능하다.
    } else if(t.x2<=x1) {
        x1 = t.x1;
        answer++;
    }
}

🔑 소스코드

import java.util.*;

public class Solution {
	
	public int solution(int[][] targets) {
        ArrayList<Target> targetList = new ArrayList();
        int answer = 0;
        
        for(int[] t : targets) {
            Target target = new Target(t[0], t[1]);
            targetList.add(target);
        }
        Collections.sort(targetList);
        
        int x1 = 100000000;
        for(int j=0 ; j<targetList.size() ; j++) {
            Target t = targetList.get(j);
            
            if(t.x1>x1) {
                x1 = t.x1;
            } else if(t.x2<=x1) {
                x1 = t.x1;
                answer++;
            }
        }
		return answer;
	}
}

class Target implements Comparable<Target> {
    int x1;
    int x2;
    
    public Target(int x1, int x2) {
        this.x1 = x1;
        this.x2 = x2;
    }
    @Override
    public int compareTo(Target t) {
        if(this.x2==t.x2) return t.x1-this.x1;
        else return t.x2-this.x2;
    }
}​