[Codility] Lesson 6: Sorting - Triangle (javascript) 문제 풀이

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : app.codility.com/programmers/lessons/6-sorting/triangle/

Triangle coding task - Learn to Code - Codility

- N 개의 정수로 구성된 배열 A 제공
- 0 ≤ P < Q < R < N이면 삼중항(P, Q, R)은 다음과 같을 경우 삼각형임
    A[P] + A[Q] > A[R],
    A[Q] + A[R] > A[P],
    A[R] + A[P] > A[Q].
- 주어진 배열 A에 삼각형이 되는 삼중항이 있으면 1을, 그렇지 않으면 0을 return
- 가장 효율적인 알고리즘 작성
- N은 [0..100,000] 범위 내의 정수
- 배열 A의 각 요소는 [-2,147,483,648..2,147,483,647] 범위의 정수

 

 

Solution

CASE 1: 배열을 정렬한 뒤, 두 수의 합보다 작은지 확인 - 81%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    const arr = A.slice();
    
    arr.sort((a, b) => a - b );
    
    for(let i=0; i<N-2; i++){
        for(let j=i+1; j<N-1; j++){
            if(arr[i]+arr[j] > arr[j+1]){
                return 1;
            }
        }
    }
    
    return 0;
}

- arr : 배열 A의 복사본 (원본을 유지하기 위해 복사본을 만들어서 사용)
- arr을 오름차순으로 정렬
- for문을 돌며 arr[i]와 arr[j]의 합이 arr[j+1]보다 크면 바로 1을 return
- for문이 다 돌게 되면 0을 return
=> 정확성은 100%지만 성능 측면에서 문제가 있음.

 

CASE 1: Result

app.codility.com/demo/results/trainingUPVNH4-ZAM/

 

CASE 1: Analysis

The following issues have been detected: timeout errors.
다음과 같은 문제가 감지되었습니다. 시간 초과 오류.

 

CASE 2: 배열을 정렬한 뒤, 두 수의 합보다 작은지 확인(예외처리 추가) - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    const arr = A.slice();
    
    arr.sort((a, b) => a - b );
    
    for(let i=0; i<N-2; i++){
      if(arr[i] < 0){
        continue;
      }
      for(let j=i+1; j<N-1; j++){
          if(arr[i]+arr[j] > arr[j+1]){
              return 1;
          }
      }
    }
    
    return 0;
}

- CASE 1에서 예외처리 추가
- arr[i]의 값이 0보다 작은 경우(음수일 경우), 비교 연산을 하지 않음

 

CASE 2: Result

app.codility.com/demo/results/trainingAUES7D-BJ9/

 

CASE 2: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

CASE 3: 단일 for문 사용 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    const arr = A.slice();
    
    arr.sort((a, b) => a - b );
    
    for(let i=0; i<N-2; i++){
      if(arr[i] < 0){
        continue;
      }
      if(arr[i]+arr[i+1] > arr[i+2]){
          return 1;
      }
    }
    
    return 0;
}

- 연이어진 세 개 항목에 대해서만 비교

 

CASE 3: Result

app.codility.com/demo/results/trainingXW5TMM-BTN/

 

CASE 3: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

결론

삼각형의 세 변 a, b, c(a가 가장 긴 변)에서 b + c > a여야 삼각형을 이룰 수 있음
=> 다른 두 변의 합(b + C)이 가장 긴 변의 길이(a)보다 큰지만 확인하면 됨!
(a가 가장 긴 변이기 때문에 a + b > c, a + c > b는 당연히 만족할 수 밖에 없음)

이 문제에는 약간의 함정(?)이 숨어있었다.
삼각형을 만들 수 있는 세 요소가 있는지 확인하는 건데 배열 A의 각 요소는 [-2,147,483,648..2,147,483,647] 범위의 정수이기 때문에 음수도 포함된 상태였다.
당연하게도 삼각형을 만들 때 음수가 있으면 말이 안되기 때문에 비교 연산을 할 때, 음수에 대해서는 비교하지 않도록 if문을 걸어주니 성능 문제도 해결됐다.

그리고 나는 정렬한 배열 arr에서 연이어지지 않은 세 항목이 삼각형이 되는 경우도 있다고 생각을 해서 이중 for문을 사용했는데(CASE 2), 생각해보니 굳이 그럴 필요 없이 for문 하나만 써서 연이어진 세 항목에 대해서만 비교(CASE 3)해주면 될 것 같다.
연이어지지 않은 세 항목도 삼각형이 될 수 있기는 한데, 그 경우에도 제일 긴 변을 기준으로 앞의 두 개 항목과 비교해도 삼각형이 될 수 있는 건 동일하기 때문이다.