Gidhub BE Developer

Programmers - 캠핑

2018-07-26
goodGid

Problem

Problem URL : 캠핑


[1] Wrong Code (18. 07. 26)


#define v vector<int>

bool inRange(v i, v j,v k){
    int in_x = 0, in_y = 0;
    if( ( i[0] < k[0] && k[0] < j[0] ) || (i[0] > k[0] && k[0] > j[0]) )
        in_x = 1;
    if( ( i[1] < k[1] && k[1] < j[1] ) || (i[1] > k[1] && k[1] > j[1]) )
        in_y = 1;
    
    return in_x * in_y ;
}

int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    int size = (int) data.size();
    sort(data.begin(), data.end());
    
    for(int i=0; i<size; i++){
        for(int j=i+1; j<size; j++){
            if(data[i][0] == data[j][0] || data[i][1] == data[j][1]) continue;
            
            int flag = 1;
            for(int k=0; k<size; k++){
                if(k == i || k == j){
                    continue;
                }
                if( inRange(data[i],data[j],data[k]) ) {
                    flag = 0;
                    break;
                }
            }
            if(flag)
                answer++;
        }
    }
    return answer;
}



[1] Wrong Code (18. 07. 26)

  • O(n^3) 이라서 시간초과가 뜰거 알았지만 inRange 함수를 만들어 보기 위해서 코딩했다.

[1] Answer Code (18. 07. 26)


int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    int size = (int) data.size();
    sort(data.begin(), data.end());
    
    for(int i=0; i<size; i++){
        for(int j=i+1; j<size; j++){
            if(data[i][0] == data[j][0] || data[i][1] == data[j][1]) continue;
            
            for(int k=j-1; k>i; k--){
               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--; // [1]
                    break;
                }
            }
            answer++; // [2]
        }
    }
    return answer;
}


[1] Answer Code (18. 07. 26)

  • [2] 코드로 인해 무조건 +1 해준다. 그렇기 때문에 안되는경우에는 [1]에서 빼주고 [2]더해주면 0이된다.

  • 틀렸을때와 큰 로직 차이는 없다.
    for(int k=0; k<size; k++) 이코드 문제였다. 어차피 i,j사이에서 겹치는 것만 체크해주면 된다.

  • 그리고 inRange함수가 시간을 굉장히 많이 잡아 먹는거 같다.

  • 또한 inRange함수에 조건문 보다는 max,min을 사용하여 조건체크하는게 효율적인거 같다.

  • 내가 푼건 O(n^3)을 최적화해서 풀었다. O(n^2) 방법 코드를 공부해야겠다.


Comments

Content