[Programmers] 겹치는 선분의 길이 풀이(JS)

 

첫번째 실패한 문제해결 방법과 이유)

0 - 200 까지의 array를 만들고, array의 index를 각 꼭지점으로 설정하여 선분이 존재하는 꼭지점에 +1씩 하엿다.

그리고 0 부터 200까지 순회를 한번 하며,  array의 요소가 연속으로 2이상이 나온다면 겹치는 선분이라고 판단하였다.

이는 선분이 아닌 양끝에 꼭지점이 있어도 선분이라고 판단되는 잘못된 생각이었다.

// 잘못된 코드
function solution(lines) {
    let arr = new Array(201).fill(0);
    for(let i=0; i<lines.length; i++){
        let point = lines[i];
        for(let j=point[0]; j<=point[1]; j++) arr[100+j]++;
    }
    let answer = 0;
    for(let i=0; i<arr.length-1; i++){
        if(arr[i] >=2 && arr[i+1] >= 2) {
            answer++;
        }
    }
    return answer;
}

위와 같은 풀이는 다음과 같은 그림의 형태일때 잘못된 답을 내놓는다.

 

 

위의 경우는 겹치는 선분이 0임에도, 꼭지점만 보고 판단하면 2라는 결과를 낸다.

 

따라서 꼭지점에 선이 존재하는 걸로 증가시키는 것이 아닌 , 선분이 존재하면 증가하는 걸로 변경하였다.

예를 들어 0-1이라는 선분이 존재하면 arr[0]++을 해주고,  2-3이라는 선분이 존재하면 arr[2]++를 해주는 것이다.

 

위를 해결한 풀이 이다.

function solution(lines) {
	// point1) 선분의 왼쪽을 기준으로 하기때문에 array는 201개로 설정한다
    let arr = new Array(201).fill(0);
    for(let i=0; i<lines.length; i++){
        let point = lines[i];
        for(let j=point[0]; j<point[1]; j++) {
        	// point2) 여기서 j는 point[1]보다 1작을때를 한계로 설정하여야 한다.
            arr[100+j]++;
        }
    }
    let answer = 0;
    for(let i=0; i<arr.length-1; i++){
        if(arr[i] >=2) {
        	// point3) 풀이방식의 의도대로 여기의 arr[i]는 arr[i]와 arr[i+1]이 선분으로
            // 이어져 있다는 것을 의미한다.
            answer++;
        }
    }
    return answer;
}

 

javascript의 더욱 간단한 메소드들을 이용하여 짧게 작성할 수 도 있지만 ,

for문 등 최대한 내 스스로 어떤 풀이인지 알아보기 쉽게 만들어봐야겠다..