[문제풀이/프로그래머스] 캠핑 (2017 카카오코드 예선)

 

 

프로그래머스

 

문제

캠핑장은 텐트를 칠 수 있는 넓은 평지를 제공하고 있는데, 이 평지에는 이미 캠핑장에서 설치해 놓은 n개의 쐐기가 박혀 있다. 캠핑장 이용 고객은 이 쐐기들 중 한 쌍을 골라 다음과 같은 조건을 만족하도록 텐트를 설치해야 한다.

- 텐트는 직사각형 형태여야 한다.
- 텐트의 네 면이 정확하게 동, 서, 남, 북을 향해야 한다.
- 대각에 위치하는 텐트의 두 꼭짓점이 정확하게 선택한 두 개의 쐐기에 위치해야 한다.
- 텐트가 점유하는 직사각형 영역의 넓이는 0보다는 커야 한다.
- 텐트가 점유하는 직사각형 영역 내부에 다른 쐐기를 포함하면 안 된다. (다른 쐐기가 경계에 위치하는 경우는 허용함)
- 캠핑장에서는 위와 같은 조건을 만족하는 위치라면 어디든 고객이 텐트를 설치할 수 있도록 정확한 크기의 텐트를 모두 구비하여 대여해준다고 한다.

당신은 위와 같은 조건을 만족하는 텐트를 설치할 수 있는 쐐기의 쌍의 개수는 총 몇 가지가 될지 궁금해졌다.
n개의 쐐기의 위치가 좌표로 주어질 때, 위의 조건을 만족하는 쐐기의 쌍의 개수를 계산하는 프로그램을 작성하시오. 단, 동서 방향은 x축, 남북 방향은 y축과 평행하다고 가정한다.

예제 입출력

n	data	answer
4	[[0, 0], [1, 1], [0, 2], [2, 0]]	3

 

풀이

먼저 두 개의 쐐기를 비교해야하기 때문에 이중 for문을 사용합니다. 그리고 방향을 쉽게 정하기 위해 x좌표 기준으로 오름차순으로 정렬합니다.

 

만약 쐐기가 위의 형태로 제공되었다면 정렬 후에는 아래와 같습니다.

[[1, 0], [3, 2], [2, 1], [0, 1]] // 정렬 전
[[0, 1], [1, 0], [2, 1], [3, 2]] // 정렬 후

기준(src) 쐐기 순회를 i, 타겟(tgt)쐐기 순회를 j일 때 j는 언제나 i+1부터 size만큼 순회합니다.

그리고 기준쐐기와 같은 X좌표이거나 같은 Y좌표인 경우에는 직사각형으로 만들 수 없기 때문에 건너뜁니다. 

#include <bits/stdc++.h>

using namespace std;
int solution(int n, vector<vector<int>> data) {
    
    // 정렬(x가 같으면 y좌표 오름차순 정렬)
    sort(data.begin(), data.end(), [](const vector<int>& a, const vector<int>& b){
        if (a[0] == b[0])
            return a[1] < b[1];
        
        return a[0] < b[0];
    });
    

    int answer = 0;
    for (int i = 0; i < n; i++) {
        const int srcX = data[i][0];
        const int srcY = data[i][1];
        
        for (int j = i+1; j < n; j++) {
            const int tgtX = data[j][0];
            const int tgtY = data[j][1];
            int diffX = tgtX - srcX;
            int diffY = tgtY - srcY;
            
            if (diffX == 0 || diffY == 0)
                continue;
                
            ...
            ...

 

예시 이미지의 쐐기에서는 C 쐐기가 A와 B로 구성된 텐트에 포함되기 때문에 이 부분을 감안해서 진행해야 합니다. 즉, 직사각형을 구성할 때 또 다른 쐐기가 직사각형 텐트에 포함되어 있는지 체크하는 프로세스가 반드시 필요합니다.

이후 i와 j 사이에 있는 쐐기들이 직사각형 안에 위치하는지 k(한번 더 반복)를 통해 찾습니다. i와 j 사이의 k 쐐기가 뜻하는 것은 만드려는 직사각형 텐트 내 또 다른 쐐기가 있는지 체크하는 의미입니다. 이미 data는 x 기준으로 오름차순 되어 있기 때문에 i와 j 사이만 보면 됩니다.

키 포인트는 k라고 볼 수 있습니다. 이미 만들어진 직사각형을 또 다른 배열에 저장해서 비교하기도 하는데, 이는 코드 복잡도를 너무 늘리기도 하고 경우에 따라 에러를 발생시킬 수도 있기 때문에 직사각형 내 다른 쐐기 탐색 방법이 더 좋습니다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;
int solution(int n, vector<vector<int>> data) {
    
    sort(data.begin(), data.end(), [](const vector<int>& a, const vector<int>& b){
        if (a[0] == b[0])
            return a[1] < b[1];
        
        return a[0] < b[0];
    });
    
    int answer = 0;
    for (int i = 0; i < n; i++) {
        const int srcX = data[i][0];
        const int srcY = data[i][1];
        
        for (int j = i+1; j < n; j++) {
            const int tgtX = data[j][0];
            const int tgtY = data[j][1];
            int diffX = tgtX - srcX;
            int diffY = tgtY - srcY;
            
            if (diffX == 0 || diffY == 0)
                continue;
            
            int minY = min(srcY, tgtY);
            int maxY = max(srcY, tgtY);
            bool flag = true;
            for (int k = i+1; k<j; k++) {
                int x = data[k][0];
                int y = data[k][1];
                
                if (x > srcX && x < tgtX && y > minY && y < maxY) {
                    flag = false;
                    break;
                }
            }
            
            if (flag)
                answer++;
        }
    }
    return answer;
}