프로그래머스 요격 시스템 C++

오랜만에 코딩테스트 문제를 풀어보았다.

가장 쉬운 문제도 풀지 못하는 것이 한스럽다.

 

1시간 정도를 투자했는데 풀지 못했다. 난이도는 실버인데, 머리가 돌아가지 않는다.

 

첫 풀이

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#define MIN(a, b) ((a<=b)?a:b)

using namespace std;

int cmp(vector <int>& v1, vector <int>& v2) {
    if(v1[0] == v2[0])
        return v1[1] < v2[1];
    else
        return v1[0] < v2[0];
    
}

int solution(vector<vector<int>> targets) {
    
    sort(targets.begin(), targets.end(), cmp);
    
    int target = targets[0][1];
    
    int answer = 0;
    
    for(int index = 1; index <= targets.size() - 1; index++) {
        
        if(target > targets[index][0]) {
            target = MIN(target, targets[index][1]);
        }
        else {
            answer++;
            target = targets[index][1];
        }
    }
    answer++;
    
    return answer;
}

보시다시피 코드가 좀 더럽다.. 이걸 끄집어 내는 데에도 꽤나 오랜 시간이 걸렸다.

아직 한없이 부족하다. 꾸준히 풀어나가야겠다.

 

 

 

 

재풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int cmp(vector<int>& v1, vector<int>& v2) {
    return v1[1] < v2[1];
}

int solution(vector<vector<int>> targets) {
        
    
    int e = 0; // 미사일 요격 끝나는 지점
    int answer = 0;
    
    sort(targets.begin(), targets.end(), cmp);
    
    
    for(auto target: targets) {
        
        if(e <= target[0]) {
            e = target[1];
            answer++;
        }
    }
    
    return answer;
    
    

}

여기선 비교함수에서 <= 를 넣었다가 Segmental fault가 계속 떠서 애를 좀 먹었다.

 

풀이는 이런 느낌이다.

전체 맵을 x축에 평행한 일직선을 그으며 경계선을 본다는 느낌으로

구간에서 요격할 수 있는게 있으면 전부 포함시키면 된다.

 

(1, 4) 범위에서 요격을 시도해야한다면 당연히 (4, 6) 범위에서는 추가로 요격을 해줘야 한다.

결국 전체 미사일에 대해 요격을 다 해줘야 하기 때문에 이건 DP가 필요하지 않는 Greedy 방식이다.

 

 

1. 종료 지점을 기점으로 오름차순으로 배열을 먼저 정렬한다.

2. 종료 지점을 기점으로 오름차순했기에 예를들어 (1, 4) (2, 8) 이런식으로 나올 것이다. 그럼 4가 2보다 작으면 함께 요격할 수 있고 그렇지 않으면 요격할 수 없으니 종료 지점을 4에서 8로 업데이트해주고 반복한다.

 

 

해당 종료 지점까지, 요격할 수 있는 미사일이 몇 개가 있는지 검사하는 과정이다.