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

---

입출력 예linesresult

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

처음 든 생각

- 겹치는 구간을 반복문을 돌면서 설정해줘야겠다.

- 근데 세개 다 겹치면 어떻게 되지...

- 벤다이어그램 세개짜리를 생각하면 안쪽의 합집합이니깐 두개씩 교집합 3개 더한거에 3개 교집합 2번 빼주면 되겠다.

 

나의 답

function solution(lines) {
    var answer = 0;
    const getLine = (a,b)=>{
        if(a[1]<=b[0] || a[0]>=b[1]){
            return [0,0]
        } 
        if(a[1]>b[0] && a[0]<=b[0]){
           return a[1]>b[1] ? b : [b[0],a[1]]
        }
        if(a[0]>=b[0]){
            return b[1]>a[1] ? a : [a[0],b[1]]
        }
    }
    const arr = [[0,1],[0,2],[1,2]]
    const overlapArr = []
    for(let i of arr){
        overlapArr.push(getLine(lines[i[0]],lines[i[1]]))
    }
    for(let i of overlapArr){
        answer += i[1] - i[0]
    }
    const tripleOverlay = []
    for(let i of arr){
        if(overlapArr[i[0]] !== [0,0] && overlapArr[i[1]] !== [0,0]){
            tripleOverlay.push(getLine(overlapArr[i[0]],overlapArr[i[1]]))
        }
    }
    answer -= (tripleOverlay[0][1]-tripleOverlay[0][0])*2
    return answer;
}

겹치는 구간을 리턴하는 getLine이라는 함수를 선언해주었다.

그리고 한번 겹치는 구간들의 배열을 반복문을 돌면서 넣어준다.

이 배열은 두개씩 교집합의 구간이니깐 일단 세개를 다 더한다.

세개 다 겹치는 구간을 찾기 위해서 두개씩 교집합 했던 애들을 한 번 더 getLine 함수를 돌린다.

그렇게 되면 (A교B)교(B교C) 이런 형식으로 가기 때문에 A교B교C가 나오게 된다. 아무거나 해도 결과는 똑같음.

 

그래서 세번 겹치는 구간의 길이를 두번 빼주면 완성이 된다.

 

참고

function solution(lines) {
    let line = new Array(200).fill(0);

    lines.forEach(([a, b]) => {
        for(; a < b; a++) line[a+100]++;
    });

    return line.reduce((a, c) =>  c > 1 ? a + 1 : a, 0)
}

조건을 보면 최대길이가 200이다.

그래서 그만큼 배열을 만들어주고 하나씩 돌면서 포함된 구간에는 1씩 더해준다.

그러면 겹치는 애들은 2나 3으로 결과값을 나타낼 것이기 때문에 1인 애들만 세주면 된다.

 

조건을 최대한 활용한 풀이여서 인상 깊다.

 

문제 상황에 따라 범위 같은 조건도 잘 확인해봐야겠다.