[Programmers] 캠핑

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/1833

프로그래머스

n이 최대 5000이라 O(n^3)으로 풀 수 없는 문제라고 생각했는데 적절한 가지치기를 진행하니 AC를 받을 수 있는 문제였습니다.

사실 문제에서 주어진대로 구현을 하고 제출을 해봤는데 얼떨결에 맞은 문제라 제대로 풀었는지 잘 모르겠습니다.

 

알고리즘은 아래와 같습니다.

1. 우선, data 벡터를 y좌표(문제에서는 x좌표라고 칭함)를 기준으로 정렬을 했습니다.

2. 쐐기의 모든 조합을 확인하고자 이차원 반복문을 작성했고

2.1 두 쐐기가 y 축이든 x 축이든 같은 선상에 있을 경우 직사각형의 넓이가 0이 되므로 제외시켰습니다.

2.2 2.1 조건에서 걸러지지 않은 쐐기 조합에 대해서도 직사각형 사이 다른 쐐기가 들어올 수 있는지 확인하고 들어올 수 있다면 제외시켰습니다.

2.3 2.1, 2.2 조건 둘 다 통과했을 경우 answer를 1 증가시켰습니다.

3. answer를 반환합니다.

 

	#include <vector>
	#include <algorithm>
	#include <iostream>
	using namespace std;
	// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
	int solution(int n, vector<vector<int>> data) {
	sort(data.begin(), data.end());
	int answer = 0;
	for (int i = 0; i < data.size() - 1; i++)
	{
	for (int j = i + 1; j < data.size(); j++)
	{
	pair<int, int> p = { data[i][0], data[i][1] };
	pair<int, int> p2 = { data[j][0], data[j][1] };
	if (p.first == p2.first || p.second == p2.second)
	{
	continue;
	}
	bool installable = true;
	for (int k = i + 1; k < j; k++)
	{
	pair<int, int> p3 = { data[k][0], data[k][1] };
	if ((p.first < p3.first && p3.first < p2.first)
	&& min(p.second, p2.second) < p3.second
	&& max(p.second, p2.second) > p3.second)
	{
	installable = false;
	break;
	}
	}
	answer += installable ? 1 : 0;
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~