[Swift 알고리즘] Triangle - Codility

Triangle coding task - Learn to Code - Codility

---

문제 분석

주어진 배열에서 삼각형을 구성하는 3개의 변의 길이가 하나라도 있으면 1, 없으면 0
 삼각형의 조건: 3개의 원소가 언제나 [2개의 합 > 1개]를 성립하는 것
 사실 큰 것끼리 더하면 당연히 성립한다.
 그러므로 3개의 원소를 정렬해서 [작은 값끼리의 합 > 큰 값]을 성립하는지만 확인하자.
 다만 원소에 음수가 있을 수 있다.
     원소에 음수가 있으면 조건이 절대 성립하지 않는다.
     작은 값이 음수일 텐데, 음수끼리의 덧셈은 값을 더 작아지게 만들기 때문에
     0의 경우도 같다.

배열 중에서 3개의 원소를 선택하는 방법을 고민해보자
 100,000 C 3은 너무 크다.
 배열을 오름차순으로 정렬해서, i, i+1, i+2를 계속 비교하는 것이 좋겠다.
     하나라도 조건을 만족하면 return 1, 없으면 return 0

의사 코드

let size = A.count
 let sortedA = A.sorted()
 for i in 0..<size - 2 // i + 2 == size - 1까지 가능하므로
 sortedA[i] + sortedA[i + 1] > sortedA[2] ? return 1
 중간에 return 못 하면, return 0

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count
    if size < 3 { return 0 }

    let sortedA = A.sorted()
    
    for i in 0..<size - 2 {
        if sortedA[i] + sortedA[i+1] > sortedA[i + 2] { return 1 }
    }

    return 0
}

회고

배열의 크기가 3보다 작은 경우를 놓쳐서, 최초 풀이 정확도가 87% 나왔다.

항상 문제의 조건을 기억하자.

더 좋은 습관은, 항상 테스트 코드를 작성할 때 다음을 고려하는 것이다.

• 값이 없는 케이스
• 값이 아주 작거나, 아주 큰 케이스
• 0, 양수, 음수가 포함되는 케이스