프로그래머스 - 겹치는 선분의 길이 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> lines) {
    
    int answer=0;
    int arr[201]={0,};
    
    for(int i=0;i<3;i++)
    {
        for(int j=lines[i][0];j<lines[i][1];j++)
        {
            arr[j+100]++;
        }
    }
    
    for(int i=0;i<201;i++)
        if(arr[i]>=2)answer++;
    
    return answer;
}

 

 설명

3개의 선분이 주어지고 이 선분들이 겹치는 부분의 길이를 구하는 문제이다.

 

배열을 하나 만들어서 각 선분에 해당하는 범위를 1씩 증가시킨다.

만약 겹치는 부분이 있다면 해당인덱스의 값이 2 이상일 것이다. 

 

int answer=0;
    int arr[201]={0,};
    
    for(int i=0;i<3;i++)
    {
        for(int j=lines[i][0];j<lines[i][1];j++)
        {
            arr[j+100]++;
        }
    }

arr배열에 각 선분의 범위를 표시한다. 

j for문에 lines[i][0] 부터 lines[i][1]-1 까지 도는 것을 볼 수 있다. 

 

아래와 같은 문제 때문이다.

 

ex) 

선분 1 : -1~2

선분 2 : 1~4

이 때, 겹치는 길이는 1이다. 그런데 j for문으로 lines[i][1]까지로 한다면 

즉, j<=lines[i][1] 로 한다면 1과 2에 해당하는 인덱스부분이 모두 1씩 더해진다. 즉 2가 된다. 

따라서 시작과 끝 중 한 곳만 1씩 더하는 것으로 해서 이 문제를 해결한다. 

 

범위가 -100 ~ 100 이기 때문에 201의 크기의 배열을 만든다. 

그리고 j에 100을 더해서 음수인 부분을 해결한다. 

 

 for(int i=0;i<201;i++)
        if(arr[i]>=2)answer++;

2 이상인 부분일 때, answer를 1 더한다. 

 

 

 

 

참고

이 문제를 혼자의 힘으로 해결하진 못했다.

처음에 배열을 하나 만들어서 길이가 2이상인 부분을 골라내면 되겠다 하고 생각했었다.

그런데 겹치는 부분의 길이가 1인 경우에서 2가 더해졌다. 왜냐하면 겹치는 부분의 시작과 끝점이 더해졌기 때문이다. 

그래서 1을 빼면 되나 생각했지만 겹치는 부분이 따로 떨어진 2개이상이라면 이 또한 몇개인지 계산해 1씩 빼줘야 한다.

그래서 다른 방법을 찾아보려했지만 결국엔 검색해서 처음 생각했던 방법에서 끝점을 범위에 포함시키지 않으면 해결이 된다는 것을 알게 되었다.