🖥️ 겹치는 선분의 길이 ➕

Buᐢ༝ᐢy 2022. 12. 13. 06:00

문제 설명

빨간색, 초록색, 파란색 선분이 x축 위에 있습니다. 세 선분의 x좌표 시작과 끝이 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를return 하도록 solution 함수를 완성해보세요.

lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 2만큼 겹쳐있습니다.

제한사항

lines의 길이 = 3

lines의 원소의 길이 = 2

모든 선분은 길이가 1 이상입니다.

lines의 원소는 [a, b] 형태이며, a, b는 각각 양 끝점 중 하나입니다.
- 100 ≤ a < b ≤ 100

입출력 예

lines	result
[[0, 1], [2, 5], [3, 9]]	2
[[-1, 1], [1, 3], [3, 9]]	0
[[0, 5], [3, 9], [1, 10]]	8

입출력 예 설명

입출력 예 #1

초록색과 파란색 선분이 [2, 5], [3, 9]로 [3, 5]만큼 겹쳐있으므로 2를 return 합니다.

입출력 예 #2

겹친 선분이 없으므로 0을 return 합니다.

입출력 예 #3

빨간색과 초록색 선분 [3, 5]부분이 겹칩니다.

빨간색과 파란색 선분 [1, 5]부분이 겹칩니다.

초록색과 파란색 선분이 [3, 9]부분 겹칩니다.

따라서 8을 return 합니다.

제출 코드

#include <string>
#include <vector>

using namespace std;

int result[201] = {};
int solution(vector<vector<int>> lines) {
    int answer = 0;
    int length = lines.size();

    for(int i = 0; i < length; i++)
    {
        for(int j = lines[i][0]; j < lines[i][1]; j++)
        {
            result[j + 100]++;
        }
    }

    for(int i = 0; i < 200; i++)
    {
        if(result[i] >= 2) answer++;
    }

    return answer;
}

이전에 백준에서 풀었던 것처럼 모든 수의 범위를 담을 수 있는 result 배열을 만들어준다. 범위가 200인 이유는 입력 범위인 -100 ~ 100까지 담을 수 있다. 음의 정수를 표현할 수 있는 배열의 인덱스는 없기 때문에 100을 더해주어 음수까지 고려해주었다.

result의 값이 1이라면 선 1개만 놓여있기 때문에 겹치지 않아 2 이상으로 범위를 잡아주었다.

➕ 재풀이

직접 생각해서 푼 건 아니다. 다른 사람들은 어떻게 풀었는지 살펴보던 중, 위 방법으로 풀지 않고 map을 이용해서 푼 방법들이 많았다. 그래서 어떻게 푸는지 이해한 후 코드를 다시 작성해보았다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<vector<int>> lines) {
    int answer = 0;
    map<int, int> result;
    
    for(auto& line : lines)
    {
        for(int i = min(line[0],line[1]);i<max(line[0],line[1]);i++)
        {
            result[i]++;
        }
    }
    
    for(int i = -100; i < 100; i++)
    {
        if(result[i] >= 2) answer++;
    }
    
    return answer;
}

아직 2차원 vector도 생소한데, map까지 사용해보니 공부할 게 엄청 많다고 새삼 느끼게 되었다. 그리고 for문을 foreach처럼 쓰는 방법도 처음 써보았는데 편리했다. 시간 날 때 자료구조들 사용법에 대해 정리하는 글을 써봐야겠다.

Uploaded by N2T