[HackerRank] Maximum Perimeter Triangle

Practice > Algorithms > Greesy > Maximum Perimeter Triangle

code

vector<int> maximumPerimeterTriangle(vector<int> sticks) {
    vector<int> result;
    int sum;
    
    sort(sticks.begin(), sticks.end(), greater<int>());
    for(int i=0; i<sticks.size() - 2; i++){
        for(int j=1; j<sticks.size() - 1; j++){
            for(int k = 2; k<sticks.size(); k++){
                if(i >= j || j >= k || k <= i)
                    continue;
                if(sticks[i] < sticks[j] + sticks[k]){
                    result.push_back(sticks[k]);
                    result.push_back(sticks[j]);
                    result.push_back(sticks[i]);
                    return result;
                }
            }
        }
    }
    
    result.push_back(-1);
    return result;
}

• 삼각형의 조건은 가장 긴 변의 길이가 다른 두 변의 길이의 합보다 작아야 한다.
• 따라서 내림차순으로 정렬한 뒤, 삼각형의 조건을 검사해 삼각형을 만들 수 있다면 result 백터에 값을 넣어 반환하였다. 
• 이때 인덱스의 번호가 i < j < k가 아니라면 가장 긴 변이 i번째의 값이 될 수 없다는 것이므로 continue로 넘어가 주었다.
• 마지막까지 함수가 종료되지 않았다면 삼각형을 만들 수 없는 것이므로 -1를 백터에 넣어 반환하였다.

결과