[프로그래머스 Level 3] 캠핑 (C++)

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

프로그래머스

 

1. x축과 y축을 기준으로 정렬 진행

2. 순서에 따라 2개의 좌표 추출(1-2-3-4와 같이 있을 때 1-2, 1-3, 1-4, 2-3, 2-4, 3-4)

3. 그 사이에 있는 좌표가 직사각형 내부에 있는지 검증

시간 초과가 날 거라 생각해서 안 했었다. 근데 다른 풀이가 안 떠올라서 인터넷을 뒤져봤는데 내가 생각한 풀이랑 똑같길래 실행해보았고, 통과가 되었다. 시간 초과 부분이 널널한 거 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    
    sort(data.begin(), data.end());
    
    for(int i = 0; i<n; i++){
        int a = data[i][0];
        int b = data[i][1];
        
        for(int j = i+1; j<n; j++){
            int x = data[j][0];
            int y = data[j][1];
            
            if(a == x || b == y) continue;
            
            bool isInner = false;
            
            for(int k = i+1; k<n; k++){
                int p = data[k][0];
                int q = data[k][1];
                
                if(p>a && p<x && q>min(b,y) && q<max(b,y)){
                    isInner = true;
                    break;
                }
            }
            if(isInner)
                continue;
            
            answer++;
        }
    }
    return answer;
}