[Programmers]#Level2_요격 시스템, 정렬, 최대 중복 구간

 

[Programmers 알고리즘, C++]#Level 2_다음 큰 숫자

 

Programmers 알고리즘 문제 풀이, Level 2_요격 시스템

정렬 작업을 통해 중복되는 구간을 최대로 설정하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

 

#2. 풀이

1. 중복이 있는 구간들 찾기

1. 먼저, s ~ e 구간 내 s값과 e값을 제외한 나머지 값들이 겹치는 미사일들을 찾아야 합니다.
2. 주어진 vector 컨테이너를 "e" 값, 즉 개구간의 최대 값을 기준으로 오름차순 정렬합니다.
3. 만약, 한 미사일의 "s" 값이 다른 미사일의 "e"값과 같거나 크다면, 두 미사일은 중복되는 구간이 없다는 의미로 해석할 수 있습니다. 반대로, 한 미사일의 "s"값이 다른 미사일의 "e" 값보다 작다면, 두 미사일은 중복되며 한 번의 요격 미사일로 두 미사일들을 요격해 방어할 수 있다는 의미죠.
4. 주의할 점은 3번과 같은 조건이 합치하려면, 주어진 배열을 "e"값으로 오름차순 정렬해야 합니다. 

 

2. sort 함수

[Basic C++] #32-3_STL 정렬 알고리즘

 

Details

 

• C++의 STL이 제공하는 sort 함수입니다.
• sort 함수는 "퀵 정렬"을 기반으로 구간의 첫 번째 요소를 가리키는 반복자와 구간의 마지막 요소의 다음 위치를 가리키는 반복자를 인자로 전달받아 오름차순 정렬하는 함수입니다. 
• sort 함수는 기본적으로 오름차순 정렬을 수행하지만, 세 번째 인자로 Predicate 함수를 전달받아 그 정렬 기준을 바꿀 수 있습니다.

 

3. vector 컨테이너

[Basic C++] #33_Vector, 순차 컨테이너

 

Details

 

• C++의 STL이 제공하는 vector 컨테이너입니다.
• size 메서드를 활용해 해당 vector 컨테이너에 저장된 원소의 개수를 확인할 수 있습니다.

 

#3. 코드

 

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

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    
    sort(begin(targets), end(targets), [](vector<int> a, vector<int> b){
        return a[1] < b[1];
    });
    
    double prev_max = -1;
    for(int i=0; i<(int)targets.size(); i++)
    {
        // 다른 미사일 추가
        if(targets[i][0] >= prev_max)
        {
            answer++;
            prev_max = targets[i][1];
        }
    }
    
    return answer;
}