Lv0. 삼각형의 완성조건 (1) - java

Lv0.삼각형의 완성조건 (1) - java

[문제링크]

https://school.programmers.co.kr/learn/courses/30/lessons/120889

✔️요구사항

선분 세 개로 삼각형을 만들기 위해서는 다음과 같은 조건을 만족해야 합니다.

• 가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 합니다.

삼각형의 세 변의 길이가 담긴 배열 sides이 매개변수로 주어집니다. 세 변으로 삼각형을 만들 수 있다면 1, 만들 수 없다면 2를 return하도록 solution 함수를 완성해주세요.

---

✔️제한사항

선분 세 개로 삼각형을 만들기 위해서는 다음과 같은 조건을 만족해야 합니다.

• 가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 합니다.

삼각형의 세 변의 길이가 담긴 배열 sides이 매개변수로 주어집니다. 세 변으로 삼각형을 만들 수 있다면 1, 만들 수 없다면 2를 return하도록 solution 함수를 완성해주세요.

---

✔️입출력 예

sides	result
[1, 2, 3]	2
[3, 6, 2]	2
[199, 72, 222]	1

• 가장 큰 변인 3이 나머지 두 변의 합 3과 같으므로 삼각형을 완성할 수 없습니다. 따라서 2를 return합니다.
• 가장 큰 변인 6이 나머지 두 변의 합 5보다 크므로 삼각형을 완성할 수 없습니다. 따라서 2를 return합니다.
• 가장 큰 변인 222가 나머지 두 변의 합 271보다 작으므로 삼각형을 완성할 수 있습니다. 따라서 1을 return합니다.

---

✔️나의 문제풀이

import java.util.Arrays;  class Solution {     public int solution(int[] sides) {         Arrays.sort(sides);         if(sides[2] >= sides[0] + sides[1]) return 2;         return 1;     } } 

• 매개변수로 받은 sides를 오름차순으로 정렬한다.
• sort() 매서드는 내부적으로 void이고 새로운 배열을 반환하는게 아니기 떄문에 sides변수 그대로 오름차순으로 정렬되게 된다.
• sides의 길이는 3으로 고정되어 있으므로 [2]번째 인덱스가 제일 큰값이 된다.
• 작은 값을 두개 더한 값이 큰값과 같거나 크면 2를 반환하고 그렇지 않으면 1을 반환하여 해결하였다.

테스트	성능
테스트 7 〉	통과 (0.33ms, 79.6MB)
테스트 8 〉	통과 (0.36ms, 73.9MB)
테스트 9 〉	통과 (0.35ms, 76MB)

---

✔️다른사람의 문제풀이 1

import java.util.Arrays;  class Solution {     public int solution(int[] sides) {         int answer = 0;         Arrays.sort(sides);         return sides[2] >= sides[0]+sides[1] ? 2 : 1;     } } 

• 풀이가 크게 다르지 않지만, 내가 푼 방법은 early return이고 다른 사람의 풀이는 3항 연산자를 써서 해결했다.
• 취향 차이겠지만, 유지보수 측면에선 전자가 더 낫지않을까 생각이 든다.

테스트	성능
테스트 1 〉	통과 (0.38ms, 71.2MB)
테스트 2 〉	통과 (0.33ms, 86.9MB)
테스트 3 〉	통과 (0.46ms, 76.3MB)
테스트 4 〉	통과 (0.44ms, 72.7MB)
테스트 5 〉	통과 (0.34ms, 81.6MB)
테스트 6 〉	통과 (0.35ms, 75.8MB)
테스트 7 〉	통과 (0.47ms, 70.2MB)
테스트 8 〉	통과 (0.50ms, 80.5MB)
테스트 9 〉	통과 (0.45ms, 66.9MB)

---

✔️다른사람의 문제풀이 2

class Solution {     public int solution(int[] sides) {         int A = sides[0] + sides[1];         int B = sides[1] + sides[2];         int C = sides[0] + sides[2];  		if(A <= sides[2] || B <= sides[0] || C <= sides[1]) return 2;         else return 1;     } } 

• sort() 매서드를 쓰지 않고 배열의 합을 계산하여 O(n)의 시간복잡도를 가진다.
• sort()매서드가 일반적으로 O(n log n)시간복잡도를 가지므로, 상대적으로 무거운 작업이다.
• 성능을 생각하여 해결한 문제로 보인다.

테스트	성능
테스트 1 〉	통과 (0.02ms, 73MB)
테스트 2 〉	통과 (0.02ms, 75.9MB)
테스트 3 〉	통과 (0.02ms, 78.1MB)
테스트 4 〉	통과 (0.02ms, 76.8MB)
테스트 5 〉	통과 (0.03ms, 83.6MB)
테스트 6 〉	통과 (0.02ms, 76.8MB)
테스트 7 〉	통과 (0.01ms, 76MB)
테스트 8 〉	통과 (0.01ms, 72.6MB)
테스트 9 〉	통과 (0.02ms, 74.8MB)

---

✔️다른사람의 문제풀이 3

class Solution {     public int solution(int[] sides) {         if(sides[1] > sides[2])         {             int temp = sides[1];             sides[1] = sides[2];             sides[2] = temp;         }          if(sides[0] > sides[1])         {             int temp = sides[0];             sides[0] = sides[1];             sides[1] = temp;         }          return (sides[0] + sides[1] > sides[2] ? 1 : 2);     } }  

• 맨 끝 원소와 중간 원소를 비교해 맨끝이 크면 처음과 중간 원소를 비비교하여 정렬을 하였다.
• 문제풀이 2번과 다르게 맨끝에서부터 선택정렬을 사용하여 배열의 운소를 정렬하여 해결하였다.
• 성능적으로는 2번과 비슷하지만, 배열의 크기가 커질수록 가독성면에서는 2번이 좋다고 생각했다.

테스트	성능
테스트 1 〉	통과 (0.02ms, 76.4MB)
테스트 2 〉	통과 (0.02ms, 78.7MB)
테스트 3 〉	통과 (0.03ms, 83.1MB)
테스트 4 〉	통과 (0.02ms, 72.5MB)
테스트 5 〉	통과 (0.02ms, 73.9MB)
테스트 6 〉	통과 (0.01ms, 78.2MB)
테스트 7 〉	통과 (0.01ms, 85.4MB)
테스트 8 〉	통과 (0.02ms, 75.4MB)
테스트 9 〉	통과 (0.02ms, 76.5MB)

---

고민

✔️sort()매서드는 내부적으로 어떤동작을 하길래 성능차이가 발생하는지 궁금해졌다.

Java의 정렬 매서드는 주로 병합 정렬을 기반으로 한다.
병합 정렬은 분할(divide and conquer)알고리즘의 일종인데 정렬할 배열을 두 개의 부분 배열로 분할한다.

이 때, 배열은 중간 요소를 기준으로 두 부분으로 나눠지게 된다. 정렬 작업이 진행되며 재귀적으로 정렬되고 더 이상 분할할 수 없을 때까지 반복된다.

병합 정렬은 안정적인 알고리즘으로, 최악의 경우에도 O(n log n )의 시간 복잡도를 가진다.

작은 크기의 배열을 정렬할 때는 삽입 정렬이 더 효율적일 수 있다. 시간 복잡도는 O(n^2)이므로 대규모 데이터에 대해서는 다른 효율적인 정렬 알고리즘을 고려해야 한다.

Java의 Arrays.sort()매서드는 배열의 크기와 형태에 따라 (병합 + 삽입)정렬 을 조합하여 사용하며, 이를 통해 최적화된 정렬을 수행한다고 한다.

---

✔️sort()인자 타입에 따라 달라진다.

인자타입이 원시타입(PrimitiveType)인 경우 DualPivotQuicksort.sort()가 사용되고, Object Type인 경우에는 TimSort.sort()가 사용 된다.

원시타입(PrimitiveType)

• DualPivotQuicksort는 이미 많이 정렬되어 있는 배열에 대해서 분할의 이점을 제데로 살리지 못하기 때문에 최악의 시간복잡도로서 O(n^2)를 갖는다.
• 최악의 시간복잡도를 갖게하는 많은 데이터셋들에 대해서도 O(n log n)을 갖게한다. 하지만 역시 완전히 보장하지는 못한다고 한다.
  
• DualPivotQuicksort는 클래스 이름과 다르게 MergeSort, InsertionSort, CountingSort를 가지고 있고, 배열에 크기마다 다르게 적용한다.

- 배열의 크기가 `286이상일 경우` `MergeSort`수행한다.    - 배열의 크기가 `286보다 작은 경우` `QuickSort`를 `MergeSort`보다 우선 수행한다.    - 배열의 크기가 `47보다 작은 경우` `InsertionSort를` `QuickSort`보다 우선 수행한다.    - byte배열의 크기가 `29보다 큰 경우` `CountingSort`를 `InsertionSort`보다 우선 수행한다.    - short, char 배열의 크기가 `3200보다 큰 경우` `CountingSort`를 `QuickSort`보다 우선 수행한다.    

---

✔️나눈 이유

• CountingSort의 시간복잡도는 O(n)으로 나와있는 정렬 중 가장 빠르다.
• CountingSort는 빠르지만 추가적인 배열을 하나 만들어야한다.

만약 int 배열에 { 1, 100, 100000 }이 있다면 겨우 3개를 정렬하기 위해서 크기가 최소 100000인 배열을 만들어야 한다.  배열의 크기가 작을 경우 이처럼 불 필요한 상황이 발생하기 때문에 어느정도 크기 이상일 경우에만 사용한다. 

byte, short,char 배열에서만 사용하는 이유는?

• 이 자료형들은 크기가 작아 배열의 값으로 들어가 범위가 작다.
• 따라서 CountingSort를 하기위해 추가하는 배열의 크기가 그만큼 작아지므로 당연히 효율적이게 된다.

결국
QuickSort, MergeSort도 마찬가지로 추가적인 배열을 고려해 적당한 크기 이상의 배열에만 사용하여 효율을 높인다.

분할 정렬은 기존 SinglePivotQuicksort보다 더 많은 케이스에 대해서 O(n log n)을 보장하는것으로 마무리하며 기회가 된다면 TimSort에 대해서도 알아보도록 해야겠다.

Java 11기준 정보라 더 높은 버전에서는 어떻게 변할지 모르겠다.

---

✔️sort(Object라면?) 추가자료

Object Type

✔️참고자료

참고1