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

문제

제한 사항

입출력 예시 및 설명

 

풀이

#include <algorithm>

// a 와 b 의 end 오름차순 비교
bool compare(const vector<int>& a, const vector<int>& b)
{
    return a.back() < b.back();
}

int solution(vector<vector<int>> targets) {
    int answer = 0;

    // 구간 별 end 기준으로 오름차순 정렬
    sort(targets.begin(), targets.end(), compare);

    // 첫 요격의 끝점을 last로 지정
    // 다음 구간의 start가 이전 last보다 작으면 같은 요격으로 처리
    // 크면 새 요격으로 처리, answer +1, last 교체
    int last = INT_MIN;
    for (const vector<int>& target : targets)
    {
        int back = target.front();
        if (last <= back)    // 새 요격 처리
        {
            last = target.back();
            answer++;
        }
        else continue;      // 같은 요격 처리
    }

    return answer;
}

 

풀이 설명

풀이 방식의 아이디어 자체는 '동일한 구간이 존재하면 하나의 요격으로 처리' 라는데서 출발한다.

따라서 이전 구간의 last, 구간의 마지막 좌표가 다음 구간의 front, 첫 좌표보다 크다면 동일한 구간이 존재하는 것으로 간주한다는 것이다.

 

이를 위해서 먼저 compare 함수를 작성하여 targets 배열의 각 end 구간을 나타내는 back() 을 통해 오름차순으로 정렬해주었다.

 

예시를 하나 들어서, targets 배열이

{ {4, 5}, {4, 8}, {10, 14}, {11, 13}, {5, 12}, {3, 7}, {1, 4} }

다음과 같이 준비되어 있다고 해보자.

{4, 5} 를 두고 봤을 때 front() 는 4, back() 은 5가 될 것인데 우리가 정렬해야 하는 기준은 back()에 따른 오름차순이다.

 

해서 algorithm 헤더 내의 sort 함수를 사용해주었고, 명확한 기준을 위해 compare 함수 또한 같이 작성해주었다.

 

여기까지 진행된다면, targets 배열은

{{1, 4}, {4, 5}, {3, 7}, {4, 8}, {5, 12}, {11, 13}, {10, 14}}

다음과 같이 정렬된다.

 

여기서 처음 아이디어를 다시 점검해보자.

이 배열들을 그림으로 나타내면

이렇게 표현할 수 있을 것이다.

 

첫 구간은 {1, 4} 이고 그 다음 구간인 {4, 5} 가 있는데, 여기서 유의할 점으로 문제에 ' 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다 ' 라는 말이다.

즉 첫 구간과 다음 구간이 4 라는 실수 좌표가 겹치기는 해도 같은 요격 미사일로 처리할 수 없다는 말이고, 그 때문에 조건 자체를 '이전 구간의 마지막 좌표가 다음 구간의 첫 좌표보다 크다면' 으로 정해야 한다는 것이다.

 

따라서 {1, 4} 와 {4, 5} 는 서로 다른 요격 미사일로 처리된다.

 

해서 요격 카운트의 코드는 다음과 같이 작성되었다.

    // 첫 요격의 끝점을 last로 지정
    // 다음 구간의 start가 이전 last보다 작으면 같은 요격으로 처리
    // 크면 새 요격으로 처리, answer +1, last 교체
    int last = INT_MIN;
    for (const vector<int>& target : targets)
    {
        int back = target.front();
        if (last <= back)    // 새 요격 처리
        {
            last = target.back();
            answer++;
        }
        else continue;      // 같은 요격 처리
    }

첫 last 는 최소값으로 설정하여 처음 구간부터 바로 카운트가 들어갈 수 있게 해주었다.

 

이후 back 에 다음 구간의 start 지점을 저장, 이전 구간의 끝지점인 last 보다 크거나 같다면, 즉 앞서 말한 조건인 '이전 구간의 마지막 좌표가 다음 구간의 첫 좌표보다 크다면' 의 반대로 지정하여 그 경우 새 요격으로 처리하도록 하여 answer++ 을 진행하고 last 를 새로 갱신해준다.

 

이렇게 코드를 마무리 할 수 있다.