[Swift 알고리즘] Codility - Triangle

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "Codility - Triangle" 문제를 풀었습니다.

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

Triangle coding task - Learn to Code - Codility

 

풀이

이번 문제는 아래 조건을 만족하는 세 수가 있는지 확인하는 문제입니다.

 0 ≤ P < Q < R < N 일 때,
1. A[P] + A[Q] > A[R]
2. A[Q] + A[R] > A[P]
3. A[R] + A[P] > A[Q]

여기에서 배열을 정렬을 하면 해결되는 두 가지 조건이 있습니다.

바로 2, 3번입니다.

정렬 후의 배열에서 2, 3번을 말로 표현하면 아래와 같습니다.

2. 가장 작은 값은 중간 값 + 가장 큰 값보다 작다.
3. 중간 값은 가장 작은 값 + 가장 큰 값보다 작다.

가장 큰 값 + @ 이므로 가장 작은 값과 중간 값은 당연히 더 작을 수밖에 없겠죠.

 

그러므로 가장 작은 값 + 중간 값 > 가장 큰 값만 체크하면 됩니다.

위 조건을 만족하는 수가 있다면 Triangle 한 쌍이 있는 것이죠.

 

단, 두 가지에 대해 주의 사항이 있습니다.

첫 번째로 각 원소의 범위입니다.

각 원소는 Int형 최소 ~ 최대 범위를 가지므로 합을 구할 때 Int64로 캐스팅해야 합니다.

 

두 번째로 문제에 반드시 3개 이상의 input이 주어진다는 조건이 없습니다.

따라서 원소가 2개일 때의 예외처리를 해줘야 합니다.

 

생각하는데 시간이 좀 들었지만 엄청 어려웠던 문제는 아니었습니다!

하지만 sorting 종류의 문제라는 것을 모르고 풀었다면 체감 난이도가 훨씬 어려웠을 거 같아요.  

sorting 단원의 문제라서 일단 sorting이 들어가겠구나 가정을 하고 생각을 해서 떠올릴 수 있었거든요.

이런 문제가 있었구나 라는 것을 기억해뒀다가 잘 써먹어야겠습니다.

 

감사합니다!

 

전체 코드

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    guard A.count >= 3 else { return 0 }

    let sortedA = A.sorted()
    var isTriangular = false
    for i in 0..<sortedA.count-2 {
        //A[R] + A[P] > A[Q] 체크
        if Int64(sortedA[i] + sortedA[i+1]) > sortedA[i+2] {
            isTriangular = true
            break
        }
    }

    return isTriangular ? 1 : 0
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.