Codility - Triangle

아래 문제는 코딜리티에서 제공하는 Sorting > Triangle의 문제입니다🧑🏻‍💻

 

문제 제시 

An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

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

For example, consider array A such that:

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

Triplet (0, 2, 4) is triangular.

Write a function:

public func solution(_ A : inout [Int]) -> Int

that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:

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

the function should return 1, as explained above. Given array A such that:

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

the function should return 0.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

 

문제 풀이

public func solution(_ A : inout [Int]) -> Int {
  let input = A.sorted(by: >)
  let count = input.count
    
  for i in 0..<count {
    if i + 3 <= count {
      if input[i] < input[i+1] + input[i+2] {
        return 1
      }
    }
  }
  return 0
}

 

사용 개념

- sort

- 삼각형 공식

- 삼항비 / 삼항자 

 

문제 후기

해당 문제는 삼각형의 기본 원리만 알면 쉽게 해결할 수 있는 문제였습니다.

특정하게 말을 한다면 삼각형의 성립 조건만 알면 해결 할 수 있죠.

삼각형의 조건은 가장 긴변의 길이보다 나머지 두변의 길이의 합이 항상 더 커야합니다.

즉 이 개념만 머릿속에 있다면 가보자구요!

배열에 들어온것을 큰 수부터 정렬해줍니다.

가장 긴변이 될 확률이 높은 수부터 아래 두 두변의 합을 비교해주면되요.

항상 가장 큰 수들의 합이 확률적으로 만들어질 확률이 가장 크니 1,2,7번 인덱스의 값을 비교할 필요가 없죠.

즉 순차적으로 연결된 값들만 비교해도 충분합니다.

그런다면 이제 반복을 돌아주며 조건을 비교하면 됩니다.

out index 오류를 내지 않도록 i+3 <= count라는 조건까지 넣어줘야 안전하게 실패하지 않습니다.

만약 삼각형을 만드는 조건이 달성되면 곧바로 1을 리턴하고 다 돌았는데도 없다면 0을 리턴해주면 됩니다.

[참고 자료]

https://app.codility.com/programmers/lessons/6-sorting/triangle/