프로그래머스 Lv 2. c++ 18118 요격시스템

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

 

 

#include <bits/stdc++.h>
using namespace std;

bool cmp(vector<int>& t1, vector<int>& t2){
    return t1[1]<t2[1];
}

int solution(vector<vector<int>> targets) {
    int answer= 0;
    int target=-1;
    sort(targets.begin(),targets.end(), cmp);
    for(auto tc: targets){
        if(tc[0]<target && tc[1]>=target) continue;
        else{
            answer++;
            target=tc[1];
        }
    }
    return answer;
}

이때에 target 이라는 값을 잡을때, 이 값은 각각의 구간에서 오른쪽 개구간의 끝 값을 기준으로 잡는데, 이때에 이 주어지는 상황에서 모든 범위가 개구간으로 주어진다는 것을 제대로 파악해야 tc[1]>=target 형태로 = 를 포함하는 식으로 작성할 수 있다. 

개구간으로 주어지기 때문에 tc[1] = target이 되는 영역이면 새로운 미사일을 발사할 필요가 없는 상황에 해당한다. 

target이 전 원소의 개구간에서 오른쪽 끝 값에 해당하기 때문에 그때에 서로 같아도 새로운 발사를 할 필요가 없기 때문이다. 

굉장히 헷갈릴 수 있는데 다시 차근차근 이해해 보도록 하자. 

 

다른 사람의 풀이를 보니, 한쪽만 고려하는 식으로 작성하는 형태의 코드를 발견했다. 

계속해서 판별하는데 사용하는 값이 해당 케이스의 개구간에서 오른쪽 끝값에 해당하니 이러한 성질을 이용해서 판별을 조금 더 간단하게 하는 풀이이다 

#include <bits/stdc++.h>

using namespace std;

bool cmp(const vector<int>& a, const vector<int>& b) {
  return a[1] < b[1];
}

int solution(vector<vector<int>> targets) {
  sort(targets.begin(), targets.end(), cmp);

  int ans = 0;
  int t = -1;
  for (auto& tar: targets) {
    if (tar[0] >= t) {
      t = tar[1];
      ans++;
    }
  }

  return ans;
}

오히려 이렇게 작성하는것이 이해가 더 잘 되고 쉬울 수 있을것 같다.