연습문제 2-1(1) 가장 둘레가 긴 삼각형의 둘레

문제 설명

N개의 정수가 배열 arr로 주어졌을 때, 이 중 3개의 숫자를 골라 이 숫자들을 변의 길이로 하여 삼각형을 만들고자 합니다.

이때, 가장 삼각형의 둘레가 가장 긴 삼각형을 찾아, 이 삼각형의 둘레를 구하려 합니다.

위 문제를 해결하는 프로그램을 구현하세요.

---

입력 형식

· arr 양의 정수가 담긴 정수 배열

---

출력 형식

· 가장 둘레가 긴 삼각형의 둘레를 정수로 반환

---

제약 사항

· 3 <= arr.length <= 1000

· 0 < arr[i] <= 100000

---

입출력 예시

· 예시1

  · 입력

      · arr = {6, 2, 12, 8, 5, 9}

  · 출력 : 29

  · 설명 : 12, 9, 8을 선택하면 가장 둘레가 긴 삼각형이 된다.

 

· 예시2

  · 입력

      · arr = {5, 19, 4, 23, 198, 34}

  · 출력 : 76

  · 설명 : 19, 23, 34를 선택하면 가장 둘레가 긴 삼각형이 된다.

 

· 예시3

  · 입력

      · arr = {1, 2, 5, 60, 50, 7}

  · 출력 : 0

  · 설명 : 어떤 세 숫자를 이용해서도 삼각형을 만들 수 없다.

---

작성 코드

class Solution211 {
    public int solution(int[] arr) {
        int n = arr.length;
        int maxPerimeter = 0;
        for (int i = 0; i < n-2; i++) {
            for (int j = i+1; j < n-1; j++) {
                for (int k = j+1; k < n; k++) {
                    if (isValidTriangle(arr[i], arr[j], arr[k])) {
                        // Math.max() 메소드는 주어진 두 개의 인자 중에서 더 큰 값을 반환한다.
                        // arr[i], arr[j], arr[k]의 합이 이전에 발견된 가장 큰 둘레(maxPerimeter)보다 크면
                        // maxPerimeter 변수를 해당 합으로 갱신해준다.
                        // 즉 if문에서 보이는 것처럼 가능한 모든 세 개의 숫자 조합에서 유효한 삼각형을 찾으면서
                        // 그 중에서도 가장 둘레가 큰 값을 maxPerimeter 변수에 저장해 나가는 것이다.
                        maxPerimeter = Math.max(maxPerimeter, arr[i] + arr[j] + arr[k]);
                    }
                }
            }
        }
        return maxPerimeter > 0 ? maxPerimeter : 0;
    }
    private boolean isValidTriangle(int a, int b, int c) {
        return a + b > c && a + c > b && b + c > a;
    }

    public static void main(String[] args) {
        Solution211 st = new Solution211();
        int[] arr = {5, 19, 4, 23, 198, 34};
        System.out.println(st.solution(arr));
        int[] arr2 = {1, 2, 5, 60, 50, 7};
        System.out.println(st.solution(arr2));
    }
}

 

정답 코드

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int solution(int[] arr) {
        arr = Arrays.stream(arr)
                .boxed()
                .sorted(Collections.reverseOrder())
                .mapToInt(i -> i)
                .toArray();

        for (int i = 0; i < arr.length - 2; i++) {
            if (isTriangleable(arr[i], arr[i + 1], arr[i + 2])) {
                return arr[i] + arr[i + 1] + arr[i + 2];
            }
        }
        return 0;
    }

    boolean isTriangleable(int x, int y, int z) {
        return x < y + z;
    }
    public static void main(String[] args) {
        Solution st = new Solution();
        int[] arr = {5, 19, 4, 23, 198, 34};
        System.out.println(st.solution(arr));
        int[] arr2 = {1, 2, 5, 60, 50, 7};
        System.out.println(st.solution(arr2));
    }
}

 

삼각형이 되기 위해서는 다음과 같은 세 가지 조건을 만족해야 한다.

1. 두 변의 길이의 합이 다른 한 변의 길이보다 커야 한다. (a + b > c, b + c > a, c + a > b)

2. 어떤 한 변의 길이가 다른 두 변의 길이 합과 같아서는 안 된다.

3. 삼각형의 각도의 합이 180도여야 한다.