프로그래머스 LV.0 겹치는 선분의 길이

프로그래머스 LV.0 겹치는 선분의 길이

https://school.programmers.co.kr/learn/courses/30/lessons/120876

프로그래머스

 

1. 문제 명

겹치는 선분의 길이

2. 문제 설명

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

lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다.

3. 제한 사항

lines의 길이 = 3

lines의 원소의 길이 = 2

모든 선분은 길이가 1 이상입니다.

lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.

-100 ≤ a < b ≤ 100

4. 예시

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

5. 기본 제공 코드

function solution(lines) {
    var answer = 0;
    return answer;
}

6. 제출한 내 답

const solution = (lines) => {
  const [first, second, third] = lines.sort((a, b) => {
    if (a[0] === b[0]) {
      return a[1] - b[1];
    } else return a[0] - b[0];
  });

  let ab = [];
  for (i = first[0]; i <= first[1]; i++) {
    if (i >= second[0] && i <= second[1]) {
      ab.push(i);
    }
  }

  let ac = [];
  for (i = first[0]; i <= first[1]; i++) {
    if (i >= third[0] && i <= third[1]) {
      ac.push(i);
    }
  }

  let bc = [];
  for (i = second[0]; i <= second[1]; i++) {
    if (i >= third[0] && i <= third[1]) {
      bc.push(i);
    }
  }

  let answer = [ab, ac, bc];

  let 중복 = [];
  for (
    i = Math.min(...[...ab, ...ac, ...bc]);
    i <= Math.max(...[...ab, ...ac, ...bc]);
    i++
  ) {
    if (ab.includes(i) && ac.includes(i) && bc.includes(i)) {
      중복.push(i);
    }
  }

  let print = 0;
  if (중복.length > 1) {
    for (i = 0; i < answer.length; i++) {
      if (answer[i].length > 1) {
        print += answer[i].length - 1;
      }
    }
    return print - (중복.length - 1) * 2;
  } else {
    for (i = 0; i < answer.length; i++) {
      if (answer[i].length > 1) {
        print += answer[i].length - 1;
      }
    }
    return print;
  }
};

 

선 a, b, c와

선을 두 개 씩 짝지었을때 겹치는 범위를 배열 ab, ac, bc로 표시하고

겹치는 범위 ab, ac, bc가 공통적으로 가지고 있는 범위를 배열 '중복'으로 표시한다

 

이 중복의 길이가 1 이하라면, 이는 그저 어쩌다 점이 만날뿐 선이 아니기 때문에

ab, ac, bc의 길이에서 1씩을 빼고 모두 더한 후 반환한다.

배열이고, 시작점과 끝점, 그리고 그 사이에 있는 지점들이기 때문이다.

 

중복의 길이가 1 초과 2 이상이라면

세 범위 ab, ac, bc가 공통적으로 가지고 있는 범위가 있다는 의미이므로

ab, ac, bc의 길에서 1씩을 빼고 모두 더한 값에서 

중복되는 범위에서 1을 빼고 2를 곱한다.

return ab.length - 1 + ac.length - 1 + bc.length - 1 - ((중복.length - 1) * 2)

 

이 중복되는 범위는 ab도 가지고 있고, ac도 가지고 있고, bc도 가지고 있으니까

셋 중 둘에서는 생략되어도 되기 때문이다.

 

코드가 너무도 지저분하지만.. 어쨌든..

 

 

6-2. VSC에 작성한 내용

const solution = (lines) => {
  // console.log("--------------구분선--------------");
  const [first, second, third] = lines.sort((a, b) => {
    if (a[0] === b[0]) {
      return a[1] - b[1];
    } else return a[0] - b[0];
  });

  // 어떻게 할까
  // 지금까지는 가상의 좌표로써 계산했지만
  // 애초에 주어진 배열로써 생각해본다면

  let ab = [];
  for (i = first[0]; i <= first[1]; i++) {
    if (i >= second[0] && i <= second[1]) {
      ab.push(i);
    }
  }

  let ac = [];
  for (i = first[0]; i <= first[1]; i++) {
    if (i >= third[0] && i <= third[1]) {
      ac.push(i);
    }
  }

  let bc = [];
  for (i = second[0]; i <= second[1]; i++) {
    if (i >= third[0] && i <= third[1]) {
      bc.push(i);
    }
  }

  // console.group('배열 lines의 요소');
  // console.log(first);
  // console.log(second);
  // console.log(third);
  // console.groupEnd();

  // console.group('선들이 겹치는 부분');
  // console.log(ab);
  // console.log(ac);
  // console.log(bc);
  // console.groupEnd();
  let answer = [ab, ac, bc];

  let 중복 = [];
  for (
    i = Math.min(...[...ab, ...ac, ...bc]);
    i <= Math.max(...[...ab, ...ac, ...bc]);
    i++
  ) {
    if (ab.includes(i) && ac.includes(i) && bc.includes(i)) {
      중복.push(i);
    }
  }

  let print = 0;
  if (중복.length > 1) {
    for (i = 0; i < answer.length; i++) {
      if (answer[i].length > 1) {
        print += answer[i].length - 1;
      }
    }
    // console.log(answer);
    // console.log(중복);
    return print - (중복.length - 1) * 2;
  } else {
    for (i = 0; i < answer.length; i++) {
      if (answer[i].length > 1) {
        print += answer[i].length - 1;
      }
    }
    return print;
  }
};

// test
console.log(
  solution([
    [0, 1],
    [3, 9],
    [2, 5],
  ])
); // 2
console.log(
  solution([
    [3, 9],
    [-1, 1],
    [1, 3],
  ])
); // 0
console.log(
  solution([
    [0, 5],
    [3, 9],
    [1, 10],
  ])
); // 8
console.log(
  solution([
    [0, 3],
    [0, 1],
    [0, 2],
  ])
); // 2
console.log(
  solution([
    [1, 12],
    [3, 6],
    [2, 4],
  ])
); // 4

 

7. 특이사항

첫번째 시도

const solution = (lines) => {
  let answer = 0;
  lines.sort((a, b) => a[0] - b[0]);
  /** 확인해야할 것
   * 배열의 요소는 3
   * 각 요소를 a, b, c라고 할 때
   * a와 b, a와 c, b와 c를 서로 비교한다.
   * 첫번째 비교에서 a[0]와 a[1] 사이에 b[0]이 있다면(a[0] <= b[0] && a[1] >= b[0])
   * 다음 단계로 진행, 없다면 드랍
   *
   * 다음 단계는 a[1]과 b[1]을 비교하여
   * a[1]이 더 크다면 b 그래프는 a 그래프의 범위 안에 존재하는 것이므로
   * b[0] ~ b[1]의 길이를 반환
   *
   * b[1]이 더 크다면 b 그래프의 시작점은 a 그래프의 범위 안이나,
   * b 그래프의 끝점은 a 그래프의 범위 밖이므로
   * b[0] ~ a[1]의 길이를 반환
   *
   */
  const overlap = (x, y) => {
    if (x[0] <= y[0] && x[1] > y[0]) {
      if (x[1] >= y[1]) {
        // answer += y[1] - y[0];
        return [y[0], y[1]];
      } else {
        // answer += x[1] - y[0];
        return [y[0], x[1]];
      }
    }
  };

  let ab = overlap(lines[0], lines[1]);
  // console.log(ab);

  let ac = overlap(lines[0], lines[2]);
  // console.log(ac);

  let bc = overlap(lines[1], lines[2]);
  // console.log(bc);

  // let arr = [[1, 2], undefined, undefined];
  // console.log(arr.filter((v) => v));

  console.log('최종');
  return answer;
};

// test
console.log(
  solution([
    [0, 1],
    [2, 5],
    [3, 9],
  ]),
);
console.log(
  solution([
    [-1, 1],
    [1, 3],
    [3, 9],
  ]),
);
console.log(
  solution([
    [0, 5],
    [3, 9],
    [1, 10],
  ]),
);

 

두 선이 겹치는 부분까지는 문제없이 구할 수 있으나

세 선이 공통적으로 가지는 범위의 값을 어떻게 구할지 생각하다가 

복잡해져 밀어버림

 

 

두번째 시도

const solution = (lines) => {
  console.log('--------------구분선--------------');
  let answer = 0;
  lines.sort((a, b) => {
    if (a[0] === b[0]) {
      return a[1] - b[1];
    } else return a[0] - b[0];
  });
  /**
   * 세 선이 공통적으로 포함하고 있는 부분이 있는가?
   * 공통적으로 포함하고 있는 부분을 어떻게 계산해낼 수 있을까?
   */

  // 두 선이 겹치는 부분을 계산
  const overlap = (first, second) => {
    // 좌표 second의 x가 좌표 first의 x~y 안에 존재할 것
    if (first[0] <= second[0] && first[1] >= second[0]) {
      // 첫번째 선과 두번째 선에 중복되는 부분이 존재하기만 한 경우
      if (first[1] <= second[1]) {
        return first[1] - second[0];
      } else {
        // 두번째 선이 첫번째 선의 범위 안에 존재하는 경우
        return second[1] - second[0];
      }
    }
    // 두 선이 겹치는 부분이 없는 경우
    else return 0;
  };

  // 1번 선과 2번 선
  let ab = overlap(lines[0], lines[1]);
  // console.group('ab');
  // console.log(ab);
  // console.groupEnd();

  // 1번 선과 3번 선
  let ac = overlap(lines[0], lines[2]);
  // console.group('ac');
  // console.log(ac);
  // console.groupEnd();

  // 2번 선과 3번 선
  let bc = overlap(lines[1], lines[2]);
  // console.group('bc');
  // console.log(bc);
  // console.groupEnd();

  const tripleOverlap = 0;
  if (조건) {
    // 어떻게하지
  }

  // 이제 겹치는 부분을 구하고 2를 곱한 다음 총합에서 뺀다
  // return (ab + ac + bc) - (겹치는 범위 * 2)

  // 세 선이 모두 겹치지 않는다면
  return ab + ac + bc;
};

// test
console.log(
  solution([
    [0, 1],
    [2, 5],
    [3, 9],
  ]),
); // 2
console.log(
  solution([
    [-1, 1],
    [1, 3],
    [3, 9],
  ]),
); // 0
console.log(
  solution([
    [0, 5],
    [3, 9],
    [1, 10],
  ]),
); // 8
console.log(
  solution([
    [0, 3],
    [0, 1],
    [0, 2],
  ]),
); // 2

다시 처음부터 적어봤으나 먼저 적었던 것과 같은 모습이 나옴..

똑같이 세 선이 공통적으로 가지는 범위를 어떻게 구해야할지가 나오지 않음

다른 방법을 생각해봐야할것 같음

 

세번째 시도

const solution = (lines) => {
  console.log('--------------구분선--------------');
  const [first, second, third] = lines.sort((a, b) => {
    if (a[0] === b[0]) {
      return a[1] - b[1];
    } else return a[0] - b[0];
  });

  // 어떻게 할까
  // 지금까지는 가상의 좌표로써 계산했지만
  // 애초에 주어진 배열로써 생각해본다면

  let ab = [];
  for (i = first[0]; i <= first[1]; i++) {
    if (i >= second[0] && i <= second[1]) {
      ab.push(i);
    }
  }

  let ac = [];
  for (i = first[0]; i <= first[1]; i++) {
    if (i >= third[0] && i <= third[1]) {
      ac.push(i);
    }
  }

  let bc = [];
  for (i = second[0]; i <= second[1]; i++) {
    if (i >= third[0] && i <= third[1]) {
      bc.push(i);
    }
  }

  // console.group('배열 lines의 요소');
  // console.log(first);
  // console.log(second);
  // console.log(third);
  // console.groupEnd();

  // console.group('선들이 겹치는 부분');
  // console.log(ab);
  // console.log(ac);
  // console.log(bc);
  // console.groupEnd();
  let answer = [ab, ac, bc];
  answer = answer.filter((v) => v.length > 1);
  if (answer.length === 0) {
    return 0;
  } else if (answer.length === 1) {
    return answer[0].length - 1;
  } else {
    let arr = [];
    answer.forEach((v) =>
      v.forEach((w) => (arr.includes(w) ? w : arr.push(w))),
    );
    return arr.length - 1;
  }
};

// test
console.log(
  solution([
    [0, 1],
    [3, 9],
    [2, 5],
  ]),
); // 2
console.log(
  solution([
    [3, 9],
    [-1, 1],
    [1, 3],
  ]),
); // 0
console.log(
  solution([
    [0, 5],
    [3, 9],
    [1, 10],
  ]),
); // 8
console.log(
  solution([
    [0, 3],
    [0, 1],
    [0, 2],
  ]),
); // 2

효율성 내려놓고 일단 풀자는 식으로 마구 적었다

1번 9번을 틀렸다.

솔직히  풀면서도 멘붕온 상태로 마구 적은거라, 답은 아직 보이지 않는다.

 

8. 다른 사람이 작성한 답

8-1.

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. lines의 원소는 [a, b] 형태이고, a와 b는 -100 이상 100 이하이니까

200의개 요소를 0으로 채운 새로운 배열 line을 만든다.

 

2. lines의 각 원소 예를 들어 [1, 7]이라면 line의 인덱스 101 원소부터 인덱스 107까지에

1을 더한다.

 

3. line의 각 원소를 검사한다.

원소가 1 이상이란 것은 lines의 반복문에서 적어도 두번 이상 영향을 받았다는 의미이므로

선이 겹쳤다고 말할 수 있다....

그리고 1 이상인 점들의 개수를 모두 구하면 답이 된다...