프로그래머스 Level 3 단속카메라

단속카메라 (프로그래머스 Level 3)

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

언젠가 보았던 여러 선들의 ‘겹치는 범위’에 대한 문제와 비슷하였다

문제에서 가장 고민한 부분은

1. 두 선은 겹치는 ‘범위’를 어떻게 특정할 것인가
   
2. 1에서 구한 범위를 어떻게 사용해서 다수의 범위를 어떻게 적용할 것인가
   

처음에 브루트포스로 생각난 것은
범위가 약 6만 내외라서 일일이 겹쳐지는 범위에 개수를 넣은 뒤
총 겹쳐지는 범위의 개수를 구해보려 하였으나
로직이 깔끔하지 못할 것 같아 포기하였다

그렇기에 ‘정렬’을 한다면 ‘탐욕’적으로 풀 수 있는 힌트가 있지 않을까?
(문제 분류가 탐욕이기에 여기서 힌트를 얻었던 것 같다)

해결 아이디어

1. 먼저 첫 요소가 작은 순으로 정렬을 하고,
   
2. queue에 집어넣어 앞에서부터 차례대로 작업할 수 있도록 자료구조 선택
   
3. 두 선이 겹치는 범위를 생각해보니,
   첫 요소 중 ‘큰 것’, 두번째 요소 중 ‘작은 것’을 택하면
   두 선의 범위가 나온다는 것을 확인 가능
   ({max(l1_x1, l2_x1), min(l1_x2,l2_x2)})
   (queue의 pop 한 녀석과 top의 녀석을 비교)
4. 그렇다면 3을 어떻게 써먹을까 하다
   ‘두 선이 겹쳤을 때’ 와 ‘그렇지 않을 때’로 나뉘어 생각
   
   • 겹치는 경우
     ‘해당하는 범위’를 새로운 ‘선’으로 인식하고
     그 뒤에 있는 녀석과 다시 비교
     
   • 겹치지 않는 경우
     별도로 카메라가 필요한 경우 이기에, answer를 하나 더해준다
     
5. queue의 top을 Ref로 가져와 ‘겹치는 경우’, 바로 덮어쓰도록 하여 구현
   

개인적으로 잠시 헷갈렸던 부분은
첫 번째 요소가 두 번째 요소와 겹치지 않지만,
세 번째 요소가 겹칠 수 있지 않을까?
라는 부분이었으나,
해당 요소들은 전부 같은 선상(1차원)에 존재하기에
‘정렬’한 경우, 존재할 수 없는 상황이라 생각하여
배제할 수 있었다

Code

#include <string>
#include <vector>
#include <queue>
#include<algorithm>
#include<math.h>

using namespace std;

int solution(vector<vector<int>> routes) {
	int answer = 1;

	sort(routes.begin(), routes.end(), [](const vector<int>& a, const vector<int>& b) {
		if (a[0] == b[0])
			return a[1] < b[1];

		return a[0] < b[0];
		});

	queue<vector<int>> q;

	for (auto a : routes)
	{
		q.push(a);
	}
	
	while (q.size() > 1)
	{
		vector<int> line1 = q.front();
		q.pop();
		vector<int>& line2 = q.front();

		bool isOverlap = false;

		if (line1[0] == line2[0])
		{
			isOverlap = true;
		}
		else if (line1[1] >= line2[0])
		{
			isOverlap = true;
		}

		if (isOverlap)
		{
			line2[0] = max(line1[0], line2[0]);
			line2[1] = min(line1[1], line2[1]);
		}
		else
		{
			answer++;
		}
	}

	return answer;
}

int main()
{
	//solution({ {-20,-15},{-14,-5}, {-18,-13}, {-5,-3} });
	//solution({ {1,2},{2,3}, {3,4}});
	solution({ {1,3},{1,2}, {2,3} });
}