[코테 풀이] Largest Perimeter Triangle

Q_976) Largest Perimeter Triangle

출처 : https://leetcode.com/problems/largest-perimeter-triangle/?envType=study-plan-v2&envId=programming-skills

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

1st Try: 시간 초과 이슈

class Solution {
    public int largestPerimeter(int[] nums) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        int p = 0;
        for (int n : nums) {
            arrayList.add(n);
        }
        Collections.sort(arrayList, Comparator.reverseOrder());
        for (int a = 0; a < arrayList.size() - 2; a++) {
            for (int b = a + 1; b < arrayList.size() - 1; b++) {
                for (int c = b + 1; c < arrayList.size(); c++) {
                    if (arrayList.get(a) < arrayList.get(b) + arrayList.get(c)) {
                        return arrayList.get(a) + arrayList.get(b) + arrayList.get(c);
                    }
                }
            }
        }
        return 0;
    }
}

• 3중 For문 사용
• 시간 초과 당연 🙃

2nd Try:

class Solution {
    public int largestPerimeter(int[] nums) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int n : nums) {
            arrayList.add(n);
        }
        Collections.sort(arrayList, Comparator.reverseOrder());
        int a = 0;
        int b = 1;
        int c = 2;
        while (arrayList.get(a) >= arrayList.get(b) + arrayList.get(c)) {
            if (c == arrayList.size() - 1) {
                if (b == arrayList.size() - 2) {
                    if (a == arrayList.size() - 3) {
                        return 0;
                    }
                    a++;
                    b = a + 1;
                    c = b + 1;
                } else {
                    b++;
                    c = b + 1;
                }
            } else {
                c++;
            }
        }
        return arrayList.get(a) + arrayList.get(b) + arrayList.get(c);
    }
}

• Pointer & while 문 사용
• 어차피 reverse sort가 되어있기 때문에 삼각형 조건을 만족하지 못했을 때 더 이상 다음 숫자 (더 작은 숫자)를 사용해서 더 확인할 필요가 없음
• 왜 이 생각을 못했을깡 🙃

3rd Try:

class Solution {
    public int largestPerimeter(int[] nums) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int n : nums) {
            arrayList.add(n);
        }
        Collections.sort(arrayList, Comparator.reverseOrder());

        for (int i = 0; i < arrayList.size() - 2; i++) {
            if (arrayList.get(i) < arrayList.get(i + 1) + arrayList.get(i + 2)) {
                return arrayList.get(i) + arrayList.get(i + 1) + arrayList.get(i + 2);
            }
        }
        return 0;

    }
}

🙈 풀이 참조한 문제