[프로그래머스] level.2 - 요격 시스템(C++)

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

내 풀이 1번

첫번째 풀이에서는 미사일 요격 범위를 점점 줄여나가다가 더 이상 범위 안에 들어올 수 있는 미사일이 없으면 요격 미사일을 추가하는 방식으로 해결했다.

 

과정

1. 미사일들을 시작 시점을 기준으로 정렬한다.

2. 첫번째 미사일을 기준으로 범위를 잡는다.

3. 다음 미사일이 범위 안에 들어왔다면, 다음 미사일의 시작점을 범위의 Start 지점으로 설정한다. 그리고 현재 범위의 end와 다음 미사일의 종료점 중 더 작은 것을 범위의 End 지점으로 설정한다.

4. 만약 다음 미사일이 범위 안에 없다면, 요격 미사일을 추가하고 2번으로 돌아가 다음 미사일을 기준점으로 잡고 과정을 반복한다.

5. 결과

코드

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

using namespace std;

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


int solution(vector<vector<int>> targets) {
    int answer = 0;
    
    // 미사일 시작점을 기준으로 정렬
    sort(targets.begin(), targets.end(), cmp);
    
    int idx = 0;
    while(idx < targets.size())
    {   
        ++answer;
        
        int start = targets[idx][0];
        int end = targets[idx][1];
        int missile_count = 1;

        for(int i = idx+1; i < targets.size(); ++i)
        {
        	// 이번 미사일이 범위 내에 있다면
            if(start <= targets[i][0] && end > targets[i][0])
            {
                ++missile_count;
                
                // 범위를 더 좁힌다.
                start = targets[i][0];
                end = min(end, targets[i][1]);
            }
            else
            {
                break;
            }
        }
        
        idx += missile_count;
    }
    
    return answer;
}

내 풀이 2번

더 간단한 다른 정답 코드가 있어서 이걸로도 풀어봤다. 이건 코드 먼저 공유하겠다.

코드

#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;
}

과정

1. 미사일들을 종료 지점을 기준으로 정렬한다.

2. 미사일을 순서대로 순회하면서 만약 현재 미사일의 시작 지점이 t 지점보다 크다면 t지점을 현재 미사일의 종료 지점으로 설정하고 요격 미사일을 추가한다. 

3. 결과

t 지점 변화 과정

(좌) 1번 코드 실행 결과    (우)2번 코드 실행 결과