Codility Lesson 6 - Triangle

문제 설명

N개의 정수로 구성된 배열 A가 주어집니다. 삼항식(P, Q, R)은 0 ≤ P < Q < R < N이면 삼각형입니다:

A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].

예를 들어 다음과 같은 배열 A를 생각해 봅시다:

  A[0] = 10 A[1] = 2 A[2] = 5
  A[3] = 1 A[4] = 8 A[5] = 20

삼항(0, 2, 4)은 삼각형입니다.

함수를 작성합니다:

function solution(A);

이 함수는 N개의 정수로 구성된 배열 A가 주어졌을 때, 이 배열에 대한 삼각형 삼중항이 존재하면 1을 반환하고 그렇지 않으면 0을 반환합니다.

예를 들어, 배열 A가 주어졌을 때

  A[0] = 10 A[1] = 2 A[2] = 5
  A[3] = 1 A[4] = 8 A[5] = 20

이면 위에서 설명한 대로 함수는 1을 반환해야 합니다. 다음과 같은 배열 A가 주어졌습니다:

  A[0] = 10 A[1] = 50 A[2] = 5
  A[3] = 1

이면 함수는 0을 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성합니다:

• N은 [0..100,000] 범위 내의 정수입니다;
• 배열 A의 각 요소는 [-2,147,483,648..2,147,483,647] 범위 내의 정수입니다.

문제 접근

배열 A 를 오름차순을 정렬한다

왜?! 오름차순을 정렬한다면 P < Q < R 이 조건을 만족한다. 그래서 아래 두조건을 무조건 만족한다.

• P + R > Q
• Q + R > P

그러므로 P + Q > R 이 조건만 확인하면 된다.

1. 배열 A 를 오름 차순을 정렬한다.
2. 배열 A 를 순회하면서 음수 일 경우는 제외한다.

3. P + Q > R 조건만 확인하여

   • 만족하면 1 반환
   • 만족하지 않으면 0 반환

function solution(A) {
  const arr = A.slice().sort((a, b) => a - b)

  for (let i = 0; i < A.length - 2; i++) {
    if (arr[i] < 0) {
      continue
    }

    for (let j = i + 1; j < A.length - 1; j++) {
      if (arr[j] < 0 || arr[j + 1] < 0) {
        continue
      }

      if (arr[i] + arr[j] > arr[j + 1]) {
        return 1
      }
    }
  }

  return 0
}