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

Gaeun·2022년 11월 17일

프로그래머스

프로그래머스 Lv.0 코딩테스트 입문

목록 보기

28/29

겹치는 선분의 길이

나의 풀이

지금까지 풀었던 문제 중에서 가장 머리 썼던 문제다. 쉬워보이는데 생각보다 너무 어려웠다!!!!🤯

문제풀이 기승전결

기

처음에는 한 배열의 end와 다른 배열의 start를 비교해서 end가 start보다 크면 겹치는 부분이 있다는 것을 중심으로 코드를 작성했다. 하지만 내가 작성하는 코드가 너무나도 복잡하고 가독성 떨어지고 멘탈 털리고 아주 머리가 터져나가서... 다른 방법을 생각했다.

승

노트에 손으로 써가면서 문제를 풀다보니 내가 직선을 그리고, 숫자를 쓰고, 각각의 선분을 그리고, 겹치는 부분을 찾는 것을 반복하고 있다는 것을 알게 되었다.

이를 컴퓨터적 사고로 바꾸니 직선을 그리는 것은 최솟값부터 최댓값까지 구하는 것, 숫자를 쓰는 것은 배열을 만드는 것(첫 숫자는 0인 인덱스, 마지막 숫자는 배열.length - 1 인덱스 - 말로 설명하려니 남들이 읽었을 땐 이해되지 않을 것 같다.), 각각의 선분을 그리는 것은 배열을 하나씩 채우는 것, 겹치는 부분을 찾는 것은 0이었던 result를 result++ 하면서 배열 내에서 2 이상인 인덱스를 찾는 것과 같다는 것을 꺠달았다.

이렇게 쓰고 다시 한번 읽어봐도 무슨 말인지 모르게 썼다 참.

전

직선을 그리는 것, 즉 빈 배열을 만들기 위해서는 최솟값과 최댓값을 구해야겠다고 생각했다. 문제 설명에 나와있는 예로 이야기하자면, [[0, 2], [-3, -1], [-2, 1]]의 직선을 그리기 위해서는 -3부터 3까지의 직선을 그려야 한다. 즉, 최댓값과 최솟값을 구해야 하는 것이다.
숫자를 쓰는 것, 즉 배열을 만들었다.

문제 설명에 나와있는 예로 이야기하자면, 숫자를 쓰는 것은 -3, -2, -1, 0, 1, 2, 3을 하나씩 쓰는 것과 같다고 생각했다.
여기에 최솟값만큼 모두 더하면 0, 1, 2, 3, 4, 5, 6이 되고 이는 우리가 만든 배열의 인덱스와 값이 같다고 생각할 수 있다.

각각의 선분을 그리는 것, 매개변수인 lines 안에 있는 배열을 꺼내고, 2에서 설명한 것처럼 최솟값이 음수인 경우엔 그만큼 더해주어 인덱스와 값을 같게 했다. 그리고 배열을 순회하며 선분을 그리는 것은 1만큼 더해주는 것으로 구현했다.
겹치는 부분을 찾는 것, 선분이 지나간 곳은 0이 아닌 숫자일 것이다. 이 숫자가 2 이상이라면 두 개 이상의 선분이 동시에 지나간 것이므로 1을 초과하는 숫자를 찾도록 했다.

개똥같이 말하는 나... 그만큼 문제가 너무 어려웠다.

결

function solution(lines) {
  // 최솟값, 최댓값 구하기
  const linesArr = [...lines[0], ...lines[1], ...lines[2]]
  const min = Math.min(...linesArr)
  const max = Math.max(...linesArr)
  
  // 최솟값부터 최댓값까지 0으로 새 배열 만들기
  // 최솟값부터 최댓값까지 그려진 직선에 숫자를 쓰는 것이라고 생각하면 됨
  const result = Array(max - min + 1).fill(0)
  
  // 체크하기 위해 배열 안의 배열(선분) 꺼내기
  for (let line of lines) {
    line.sort((a, b) => a - b)
    // 최솟값이 0보다 작은 경우, 양수로 만들어 인덱스를 셀 수 있도록 바꾸어주기
    // 즉, 선분이 0부터 시작하는 걸로 바꾸어주기
    if (min < 0) {
      line[0] += Math.abs(min)
      line[1] += Math.abs(min)
    }
    
    // 배열 순회하며 선분이 지나가는 곳을 1씩 증가시키기
    for (let i = line[0]; i < line[1]; i ++ ) {
      result[i] ++;
    }
  }
  
  // 2 이상인 곳은 선분이 겹쳤다는 의미
  return result.filter(x => x > 1).length;  

}

다른 사람의 풀이

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)
}