[LeetCode] 611. Valid Triangle Number

https://leetcode.com/problems/valid-triangle-number/

Valid Triangle Number - LeetCode

Valid Triangle Number.

 

문제는 참 쉽다.

배열에서 세 개의 수를 뽑아 변의 길이로 할 때, 만들 수 있는 삼각형의 개수를 묻는 문제다.

삼각형의 결정 조건은 가장 큰 변의 길이 > 나머지 두 변의 길이의 합 이므로..

어 뭐야? 엄청 쉽네?

하고 for 문을 세 개를 돌린 난.. 바로 Time limit Exceeded를 먹었다.

사실 생각해보면 간단하다. for문이 세개니 시간복잡도가 O(n^3)가 되고, 배열 길이가 1000이므로 거의 10억에 가까운 시간이 소요된다.

그러고나서는 멘붕에 빠졌다.

이걸 어떻게 해야하지..?

 

일단 첫번째로 정렬을 해주었다. => O(n^2)

벡터이므로 아래와 같이 해준다.

sort(nums.begin(), nums.end());

정렬을 하고 나면 조금 쉽게 보인다.

 

1. 첫 번째(i), 두 번째 수(j)를 고정시키고, 세 번째 수(k)를 쭉 훑어본다.

2. 이 때, 삼각형 결정조건이 맞다면 k를 한 칸씩 증가시킨다.

3. 삼각형 결정조건에 벗어난다면 개수에 k-j-1 을 증가 시키고, j를 한 칸 전진시킨다.

4. j가 배열의 마지막에 닿을때까지 2,3을 반복한다. (배열에 마지막에 닿아도 어차피 개수에 포함되지 않는다.)

5. i를 증가시킨다.

 

언뜻 보면 i,j,k를 for로 돌린 것과 마찬가지가 아닌가? 싶지만 그렇지 않다.

j가 증가할 때 k가 초기화 되지 않고 이전 자리에 그대로 있기 때문이다.

따라서 전체 과정은 O(n^2)이 된다.

 

한 가지 더 주의할 점은 i의 수가 0이 될 수도 있다. 당연히 삼각형이 성립안된다. 0을 제외해주자.

 

 

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int cnt=0;
        sort(nums.begin(),nums.end());
        if (nums.size()>2) {
            for (int i=0; i<nums.size()-2; i++) {
                if (nums[i]>0) {
                    for (int j=i+1,k=i+2; j<nums.size()-1; j++) {
                        while (k<nums.size() && nums[i]+nums[j]>nums[k]) k++;
                        cnt += k-j-1;
                    }
                }
            }
        }
        return cnt;
    }
};