Lv 0. 겹치는 선분의 길이. *다시 풀어보기*

 

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

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> lines) {
    int answer = 0;
    int a[210]={};
    for(auto t:lines){
        int st=t[0];
        int en=t[1]; // st<en 이 보장됨.
        for(int i=st; i<=en;i++){
            a[i+100]++;
        }
    }
    int tmp=-1;
    for(int j=0; j<210; j++){
        if(a[j]>=2) tmp++;
        else {
            if(tmp>=0) answer+=tmp;
            tmp=-1;
        }
    }
    sort(lines.begin(),lines.end());
    //아래의 경우가 가운데 있는 선분이 길이가 1이고, 그때에 양 끝에서 다른 선분의 양 끝에 겹쳐지는 경우가 예외처리를 해주어야 하는 부분
    if((lines[1][1]-lines[1][0]==1)&& (lines[0][1]==lines[1][0]&&lines[1][1]==lines[2][0])) answer--;
    return answer;
}

위와 같은 코드를 작성해서 통과하였는데, 스스로 생각하기에 그렇게 만족스럽지 않은 풀이이다. 아무래도 저 예제처리 해주어야 하는 부분에 대해서 제대로 생각하지 못했기 때문에, 처음에 작성한 코드의 경우는 아래에 첨부한 것처럼 그런 예외처리 부분이 없는 형태의 프로그램을 작성하였고, 그랬기 때문에 예를들어, [[1,2],[2,3],[3,4]] 형태처럼 가운데에 있는 선분이 길이가 1이 되는 경우이면서 양 끝에 있는 선분과 딱 끝 점만 연결지어지면, 내가 만든 형태의 프로그램의 경우는 수들이 0 0 0 1 2 2 1 0 0  형태처럼 나와버려서, 이 경우 answer의 값이 +1 을 해버리게 되서 결과가 잘못되기 때문에 해당 경우 같은 케이스가 되면 그 예외를 제거해주기 위해서 저렇게 예외처리 형태를 넣게 되었다. 

 

이런 특별한 예외에 대해서 제대로 고려하지 않고 위와 같은 판별 프로그램을 작성했는데 애초부터 예외가 이렇게 나올 수 있으니 주의하면서 위와 같은 로직으로 작성하자, 라고 생각했다면 오히려 괜찮았겠지만 그게 아니라 아쉬움이 남는다. 

 

/* 한참 잘못된 부분을 찾지 못한 코드 */
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> lines) {
    int answer = 0;
    int a[210]={0};
    // sort(lines.begin(),lines.end());
    for(auto t:lines){
        int st=t[0];
        int en=t[1]; // st<en 이 보장됨.
        for(int i=st; i<=en;i++){
            a[i+100]++;
        }
    }
    for(int i=0; i<210; i++){
        cout<<a[i]<<' ';
    }
    int tmp=-1;
    for(int i=0; i<=210; i++){ //맨 마지막께 체크가 안되나? 혹은 불필요한 마지막이 체크가 되나? 
        if(a[i]>=2) tmp++;
        else {
            if(tmp>0) answer+=tmp;
            tmp=-1;
        }
    }
    return answer;
}

 

다른 사람의 풀이를 보니까, 나와 비슷한 방식으로 해결한 사람들의 풀이도 있는데, 이때에 이러한 예제를 발생시키지 않게 하는 형태로 코드를 작성한 것들이 있어서 첨부해보도록 하겠다. 

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> lines) {
    const int BIAS = 100;

    vector<int> arr(BIAS*2 + 1,0);

    int answer = 0;
    for(auto& v : lines)
    {
        if(v[0] > v[1])
        {
            swap(v[0],v[1]);
        }
        for(int i = v[0]; i < v[1]; ++i)
        {
            arr[BIAS + i]++;
        }
    }

    for(const auto v : arr)
    {
        answer += v > 1;
    }

    return answer;
}

내 코드의 경우는, 시작점과 끝점까지 모두 arr[i+100]++ 형태로 작성해서 양족 끝이 모두 숫자가 증가하는데, 위의 코드의 경우는 시작점만 포함, 끝점은 제외하였기 때문에 배열을 돌면서 answer에 arr[i]>1; 인 경우에 해당하는 경우만 참 거짓 형태로 거짓이면 0, 참이면 1을 더해주는 형태로 작성했는데, 이 경우 내가 작성한 코드같은 경우 걸러내지 못하는 부분에 문제가 발생하지 않는 형태이다. 

 

위와 같은 코드를, 내게 익숙한 형태로 다시 작성해서 첨부해보자면, 

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> lines) {
    vector<int> arr(201,0);

    int answer = 0;
    for(auto& v : lines){
        for(int i = v[0]; i < v[1]; ++i){
            arr[i+100]++;
        }
    }
    for(const auto v : arr){
        answer += v > 1;
    }
    return answer;
}

위와 같은 형태이다. 이게 내가 작성한 코드보다 훨씬 간결하고 이해하기 쉽고, 직관적으로 이해가 되는것 같다. 처음에 생각한데로 선분을  배열에 +1 형태로 작성하는 방법을 떠올렸을때, 맨 끝단의 경우 어떤식으로 처리할지에 대해서 한번 더 고려해서 생각해보았다면 좋았을것같다. 다음에는 한번 더 고려해서 과연 꼭 실제처럼 맨 끝단까지 +1 처리로 표시해야 하는지에 대해서 생각해보도록 하자. 

 

  Comments,     Trackbacks