LeetCode Swift - 611. Valid Triangle Number_Greedy

주어진 수를 이용해서 삼각형을 최대 몇개나 만들수 있을지 알아보는 문제다.

나는 여전히 시간복잡도, 공간복잡도를 먼저 따져보면서 문제 푸는 스타일이 아니라... 일단 풀었다.

그래서 처음엔 Combi를 사용했고 항상 그랬듯이 Greedy문제에 Combination, Permutation이 나온다면 시간 오류가 뜰 확률이 매우매우 높다. 풀면서도 그걸 느꼈지만 일단 풀었고 역시나 일부 문제는 넘어갔지만 시간에 발목을 잡혔다.

그래서 이를 풀기 위한 다른 방법이 뭐가 있을까 고민하다가 그냥 For문을 덜 중첩시켜 풀어보기로 했다.

 

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 먼저 숫자를 올림차순으로 정리해준다.
2. i, j, k를 각각 0, 1, 2 이런 연속된 순서의 idx로 만들어준다.
3. k+1이 집합 원소의 개수보다 작고 sortedNums[i] + sortedNums[j]가 sortedNums[k+1] 보다 작으면 삼각형이 성립된다.
4. 이때 k에 1을 더해주고 이를 반복한다.
5. 이러면 k가 움직일 수 있는 최대의 범위까지 움직이게 되고
6. 그 후 j를 1씩 증가시켜 i**j**k, i***j*k, i****jk 이런 식으로 j를 이동시킨 뒤 값이 성립하는지 확인한다.
7. 이를 같은 방식으로 k를 증가시키고 j의 위치가 바뀔 수록 경우의 수도 줄어듬으로 k-j 만큼을 ans에 더해준다.

 

* 코드

class Solution {
    func triangleNumber(_ nums: [Int]) -> Int {
        let sortedNums = nums.sorted()
        var ans = 0
        
        for i in 0..<sortedNums.count {
            var k = i + 1
            
            for j in (i+1)..<sortedNums.count {
                while k+1 < sortedNums.count && sortedNums[k+1] < sortedNums[i] + sortedNums[j] {
                    k += 1
                }
                
                if sortedNums[k] < sortedNums[i] + sortedNums[j] {
                    ans += max(0, k-j)
                }
            }
        }
        return ans
    }
}

 

 

정리(Today I Learned)

1. 뭔가 아슬아슬하게 풀었다고 생각한다. 애초에 for문이 두 번이나 겹치고 while도 있어서...
   더 나은 방법이 있을 것 같다.