이전에 포스팅한 정석 풀이 말고 다른 풀이를 보여드리겠습니다. 다른 정답들을 보다가 출제의도와는 다르지만 최적화를 통해 시간내에 풀었고(하지만 시간 차이는 꽤 납니다), 코드도 깔끔하니 예뻐서 포스팅 합니다. 파란색의 주석을 보면서 읽으시면 이해하기 쉬울꺼에요.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#"차승진" 님의 풀이 입니다.
#include <vector>
#include <algorithm>
 
using namespace std;
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    sort(data.begin(), data.end()); // 좌표를 x값을 기준으로 오름차순 정렬
    for(int i=0; i<n; i++){
        for(int j=i; j<n; j++){
            if(data[i][0] != data[j][0] && data[i][1] != data[j][1]){ // 두 쌍의 쐐기가 대각선을 이루면
                for(int k=j; k>=0; k--){ // x축으로 두 쌍의 쐐기의 내부(경계선 포함)에 존재하는 쐐기를 대상으로 조건 검사
                    if(data[k][0] < max(data[i][0],data[j][0]) && // 내부에 존재하는지 검사
                       data[k][0] > min(data[i][0],data[j][0]) &&
                       data[k][1] < max(data[i][1],data[j][1]) &&
                       data[k][1] > min(data[i][1],data[j][1])){
                        answer--; // 내부에 존재하면 마이너스
                        break;
                    }
                }
                answer++; // 내부에 쐐기가 없으면 플러스
            }
        }
    }
 
    return answer;
}

코드가 깔끔하죠? 저는 보면서 이해가 안갔던 부분이 2 군데 있었습니다.

  1. for(int k=j; k>=0; k–) 쐐기 쌍을 선택한 후에, 나머지 N-2개의 쐐기쌍을 대상으로 조건 검사를 해야될꺼 같은데 그게아니라 2번째로 선택된 쐐기를 기준으로 하나씩 빼오면서 검사를 하더라고요. 그 이유를 생각해보니 좌표가 x축 우선으로 정렬이 되어있고, 내부를 검사하는 것이 목적이기 때문에 2번째 쐐기를 넘어가는 값들은 어차피 내부에 있을 수가 없기 때문입니다. 추가적으로, for의 조건식을 0에서 i로 수정하면 for(int k=j; k>=i; k–) , 조건을 검사하는 쐐기의 범위를 더 줄일 수 있습니다.x축을 기준으로 [두번째 쐐기,0] -> [두번째 쐐기,첫번째 쐐기] 로 바뀌게 됩니다. 확실히 수행시간도 줄어드네요. 2.answer–; // 내부에 존재하면 마이너스 break;조건을 만족하면 카운트를 플러스만 하면 되는데 왜 조건이 틀린경우에 마이너스를 하는지 의문이였습니다. 그리고 왜 break;가 되는지 의문이였습니다. 구조를 잘 보니, 조건을 만족하던 만족하지 않던 무조건 플러스가 되는데요. 조건을 만족하지 않는 경우에는 마이너스를 해줘서 결국에는 0가 되도록 하기 위함이였습니다. 그리고 다른 쐐기를 검사하지 않고 break를 하는 이유는 내부쐐기의 개수에 상관없이 하나라도 발견되면 조건을 만족하지 못하기 때문입니다.