[프로그래머스] 캠핑

캠핑

문제)

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

풀이)

처음에 서로 대각선에 위치해 있는 쐐기들만 골라서 텐트를 쳐야하는지 착각해서 헤맸던 문제이다.

과정

1. 쐐기의 좌표들을 오름차순으로 정렬해준다. 

2. 각 쐐기마다 다른 쐐기들과 비교하여 텐트를 칠 수 있는지 확인해준다.

  => 삼중포문을 이용해서 풀어줬다.

       for(int i=0; i<data.size(); i++) //기준 쐐기 위치 {y,x}

for(int j=i+1; j<data.size(); j++) //비교할 쐐기 위치 {ty,tx}

for(int k=i+1; k<j; k++) //기준쐐기와 비교할 쐐기 사이에 존재하는 쐐기 위치 {ky,kx}

             만약 중간에 존재하는 쐐기{ky,kx}가 기준쐐기와 비교할 쐐기가 이루는 직사각형 범위 내에 존재하면

             기준 쐐기 {y,x}와 비교할 쐐기{ty,tx}는 쌍을 이루지 못한다.

코드)

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    sort(data.begin(),data.end());
    for(int i=0;i<data.size();i++){
        int y = data[i][0];
        int x = data[i][1];
        //cout << "******확인 좌표 :" << y << " ," <<x << endl;
        for(int j=i+1;j<data.size();j++){
            int ty = data[j][0];
            int tx = data[j][1];
            if(ty == y || tx == x) continue;//같은 라인에 있으면 직사각형의 넓이 0
            //cout << " -" << ty << ", " << tx << endl;
             
            bool suc = true;
            
            for (int k = i + 1; k < j; k++){//{y,x} 와 {ty,tx}사이에 있으면서 같은 영역내에 있는가
                int ky = data[k][0];
                int kx = data[k][1];
               
                if ((y < ky && ky < ty)){
                    if(min(x,tx) < kx && kx < max(x,tx)) {
                        suc = false;
                        break;
                    }
                 }
            }
           
            if(suc) {
                //cout << "성공" << endl;
                answer++;
            }
        }
    }
    return answer;
}