겹치는 선분의 길이

링크

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

풀이

• 이문제는 실수로 풀었는데 왜 맞는지 이해가 안된다.
  • 혹시 이러한 방식이 왜 정답이 되는지 아시는분은 댓글로 알려주세요!
• 풀이 과정은 여러개의 점으로 이루어지는 선분 세개를 모두 점의 갯수로 표현해 하나의 맵에 합쳐 저장한다. 이때 각 선분의 오른쪽 끝값을 1씩 줄인 상태에서 저장한다.
  • 말로 표현한거보다 코드로 보는게 이해하기 편함.
• 세개의 선분 [[0,3],[0,3],[0,3]] 이 주어지면 위 과정을 행하면 하나의 맵 변수 m에 다음과 같이 저장된다.
  • m[0]: 3, m[1]: 3, m[2]: 3
  • 실제 세개의 선분은 길이 3의 0부터 3까지로 이루어져있지만 위와같이 저장됨.
• 마지막으로 2개이상 겹치는 길이를 원하므로 m[i]의 값이 1보다 큰 값의 갯수를 반환하면 정답이된다.
• 위의 경우엔 3개다 모두 1보다 크므로 3.

코드

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

using namespace std;

int solution(vector<vector<int>> lines) {
    int answer = 0;
    map<int, int> m;
    for(const auto &line: lines) {
        for(int i=line[0];i<line[1];i++) {
            m[i]++;
        }
    }
    for(const auto &i: m) {
        if(i.second>1) {
            answer++;
        }
    }
    return answer;
}

• 실수로 어쩌다보니 풀게 되었는데 과정은 이해 되지만 어떤 원리로 이게 항상 정답인지는 모르겠습니다.
• 혹시라도 아시는분은 댓글로 설명해주신다면 감사하겠습니다! 또는 반례가 있으신분도 환영입니다!