[코딜리티] Triangle (JavaScript)

 

문제 출처

문제 요약

A 배열이 주어질때

0 ≤ P < Q < R < N and:

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

위 조건을 만족하는 값이 있으면

return 1

없으면 return 0

처음에 갯수를 return 하라는 줄 알고 실패함...

문제 풀이

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let result = 0
    for(let p = 0; p < A.length - 2; p++){
        for(let q = p + 1; q < A.length - 1; q++){
            for(let r = q + 1; r < A.length; r++){
                const P = A[p]
                const Q = A[q]
                const R = A[r]

                if(P + Q > R && Q + R > P && R + P > Q){
                    ++result
                }
            }
        }   
    }
    return result
}

인덱스에 대한 조건이 있어서 고려해야 될것 같지만 인덱스는 중복 되지만 않으면 괜찮다.

즉 정렬하여 인접한 3개의 값 원소만 확인 하면 된다.

예제의 배열을 정리하면 1, 2, 5, 8, 10, 20으로 정렬되고, 인접한 세개의 인덱스간의 조건을 충족하는지 확인

비교해야 되는 경우는

1, 2, 5, 8, 10, 20

1, 2, 5, 8, 10, 20

1, 2, 5, 8, 10, 20

1, 2, 5, 8, 10, 20

와 같이 4가지 경우입니다.

그리고 4가지 경우에서 문제에 조건을 만족하는 경우는 1, 2, 5, 8, 10, 20가 있습니다.

그런데 이미 배열이 정렬되어 있기 때문에, 세가지 경우를 모두 확인하지 않고, 작은 인덱스 2개의 합과 나머지 큰 인덱스의 값만 비교하면 됩니다.

5 + 8 > 10 인 경우가 참이라면, 나머지 경우는 당연히 참일 수 밖에 없습니다.

핵심 : 2개 원소의 합이 나머지 하나 보다 커야 되기 때문에 제일 작은 2개의 원소의 합으로 구합니다.

결론

• 0 ≤ P < Q < R < N 이 조건 때문에 인덱스를 고려해야 되는 문제로 오해 해서 정렬 할 생각을 못했다.

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

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

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

이 조건 으로 인해 인덱스와 상관없이 2개 원소의 합이 나머지 하나 보다 크기만 하면 된다.

• 문제를 제대로 이해해야 한다. ㅠ ㅠ