[프로그래머스 | JavaScript] 겹치는 선분의 길이

<문제 설명>
선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[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

<문제 풀이>

*이 코드는 정답이 아닙니다. 정답은 아래에 있습니다.

function solution(lines) {
    let lineNum = []
    let crossNum = []
    let resultNum = []
   for(let i = 0; i < lines.length; i++){
       for(let j = lines[i][0]; j<= lines[i][1]; j++){
           lineNum.push(j)
       }
   }lineNum.sort((a,b)=>a-b)
    for(let i = 0; i < lineNum.length;i++){
        if(lineNum[i]===lineNum[i+1]){
            crossNum.push(lineNum[i])    
        }
    }
  return lineNum
}

내가 푼 방법은 각 선분의 좌표를 한 배열에 모았다. 

예시에 있는대로 예를 들면, -3,-2,-1,-2,-1,0,1,0,1,2가 lineNum에 모인다. 

그리고 순서를 정렬했다. 정렬하면 -3,-2,-2,-1,-1,0,0,1,1,2가 된다. 

 

좌표가 2개 이상 이라는 것은 겹치는 부분이라는 것이다. 

겹치는 부분만 아래에 있는 i번째 배열과 i+1번째 배열을 crossNum에 담았다. 

인덱스i와 바로 오른쪽 i가 같은 값일 경우 겹치는 것이다. 

그렇게 하면 -2,-1,0,1이 남는다. 

예시에서 겹치는 구간은 -2 ~ -1, 0 ~ 1이다. 

그런데, 여기서부터 문제가 생긴다. 겹치는 구간을 구할 때, 좌표로 구했기 때문에

-2부터 1까지의 거리를 구하는 것이 아니라, -2부터 -1까지, 그리고 0부터 1까지 구하는 것이기 때문에 

중간에 -1부터 0까지의 값은 제외해야 하는데 도저히 해결할 방법을 생각하지 못했다. 

 

다른 해결방법을 보니 기본적으로 접근은 비슷했는데,

문제가 되는 부분은 겹치는 점이 아니라 선분을 구하는 것이다.

 

다음은 정리된 코드이다. 

function solution(lines) {
  var answer = 0;
  let lineMap = new Array(200);  // 선분들이 놓일 공간
  lineMap.fill(0);

  for (let i = 0; i < 3; i++) {
    let left = lines[i][0];
    let right = lines[i][1];

    for (let j = left; j < right; j++) {
      lineMap[j + 100] += 1;
    }
  }

  for (let i in lineMap) {
    if (lineMap[i] > 1) {
      answer += 1;
    }
  }

  return answer;
}

먼저 lineMap에 200개의 요소를 가진 배열을 생성하고, 각 요소는 0을 넣는다. 

제한사항에 -100 ~ 100의 범위가 주어졌기 때문에 가능한 좌표를 모두 담으면 200개이다. 

 

그리고 좌표의 왼쪽, 오른쪽 값을 각각 배열에 담는다. 

왼쪽에서 시작해서 오른쪽으로 끝나는 값을 반복문으로 돌린다. 

여기서부터 내가 해결한 부분과 달라지는데,

200개의 0이라는 요소를 가진 배열의 j+100번째 값을 1로 바꿔줄 것이다.

그 이유는 j의 값이 -100부터 시작하는데, lineMap의 첫번째 인덱스는 0이기 때문에

적어도 -100의 값을 더해주어야 한다. 

여기까지 실행하게되면, lineMap은 각 선분이 지나가는 지점을 전부 1을 더한다. 

lineMap의 값은 0,0,0,0,0,0,0... 이였다가 선분이 놓여지면 해당 위치가 1로 바뀌는 것이다. 

선분은 3개이기 때문에 i의 값인 0,1,2라는 3개의 선분을 얹고, 그 중 겹치는 값을 찾게 된다.

그렇게 되면 선분이 놓일 때마다 1씩 늘어나기 때문에 lineMap에는 0~3의 숫자가 기록될 수 있다. 

이 중에서 lineMap의 요소가 1보다 클 경우, (겹치는 경우)

answer에 1을 더하여 겹치는 부분의 길이를 구한다. 

 

<코멘트>

 

결국 이 코드도 겹치는 좌표를 카운트하여 값을 구하게 되는데,

지날 수 있는 모든 좌표를 0으로 설정한 다음 지나게 되는 좌표에 1씩 늘리느냐,

실제 값을 나열하고 그 값이 2개 이상인 값을 추리느냐의 차이가 있었다. 

 

그렇게 되면 사실 방법의 차이인데, 결과를 구하는 과정이 달랐다.

나는 겹치는 좌표값에서 해당 값의 거리를 계산하려 했는데,

꼭짓점은 겹치는데 선분이 겹치지 않는 경우에 대한 해결을 하지 못했다. 

예시에서도 총 -3,-2,-2,-1,-1,0,0,1,1,2의 값이 나온다. 

그 중 가운데에 값이 중복되는 -2,-1,0,1이 겹치는 좌표인데, -1 ~ 0은 제외해야 했다. 

 

해결되는 후자의 코드에서는 값이 1보다 클 경우, 즉 겹치는 경우 겹치는 거리로 1을 늘렸다. 

솔직히 아직 값이 다른 이유를 모르겠다.

내가 계산한 코드가 틀린 이유는 알겠는데 해결이 되는코드가 정답인 이유를 모르겠다. 

처음 0으로 초기화된 상태에서 선분 얹을 때마다 그 위치에 1을 더하고, 2이상인 값을 구하는데

결국 그러면 겹쳐지는 -2,-1, 0, 1 에 값이 다 더해져야 하는데 왜 그렇지 않은지.. 

 

혹시라도 설명해주실 수 있는 분은 댓글로 남겨주시면 감사하겠습니다..^^