프로그래머스 0단계 - 겹치는 선분의 길이

문제 설명

선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요.

제한사항

• lines의 길이 = 3
• lines의 원소의 길이 = 2
• 모든 선분은 길이가 1 이상입니다.
• lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.

입출력 예 설명

입출력 예 #1

• 두 번째, 세 번째 선분 [2, 5], [3, 9]가 [3, 5] 구간에 겹쳐있으므로 2를 return 합니다.

입출력 예 #2

• 겹친 선분이 없으므로 0을 return 합니다.

입출력 예 #3

• 첫 번째와 두 번째 선분이 [3, 5] 구간에서 겹칩니다.
• 첫 번째와 세 번째 선분 [1, 5] 구간에서 겹칩니다.
• 두 번째와 세 번째 선분 [3, 9] 구간에서 겹칩니다.
• 따라서 [1, 9] 구간에 두 개 이상의 선분이 겹쳐있으므로, 8을 return 합니다.

1. 문제 이해

• lines의 길이가 3을 넘지 않고 선분의 길이가 10^2을 넘지 않기 때문에 시간복잡도는 문제 없어보인다.
• 선분이 두 개 이상 겹치는 모든 길이의 합이기 때문에 두 개이상 겹치도 세 개 이상 겹쳐도 그 겹치는 구간은 하나만 계산해야 한다.

2. 접근 방법

• 직관적으로 생각하기

3. 코드 설계

• 직관적으로 생각하기

4. 코드 구현

function solution(lines) {
  const linesArr = lines.map((line) =>
    [...Array(line[1] - line[0])].map((_, i) => line[0] + i + 1)
  )

  const line1AndLine2 = linesArr[0].filter((v) => linesArr[1].includes(v))
  const line2AndLine3 = linesArr[1].filter((v) => linesArr[2].includes(v))
  const line3AndLine1 = linesArr[2].filter((v) => linesArr[0].includes(v))

  return [...new Set([...line1AndLine2, ...line2AndLine3, ...line3AndLine1])]
    .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)
}

회고

처음에 문제 접근 했을 때는 더하기 빼기로 시작해서 여러가지 경우의 수를 모두 체크해서 해결하려고 했었다. 그리고 1시간이 넘게 지났고, 답을 확인하고 빠르게 넘어갈까 하다가 16시간 정도 다른 일을 하다가 다시 문제를 보고 다른 시각으로 접근해서 해결했다. 여기서 중요한 점은, 일단 하루에 1문제를 무조건 풀어야지라는 기준 때문에 깊게 생각해 볼 수 있는 시간을 뺐을 수도 있었다는 것이다. 그러니, 기준을 다시 잡도록 하자. 하루에 1시간씩 3일 동안 문제를 풀어보려고 노력했다가 안되면 답안을 보는 걸로!!