Lesson6 - MaxProductOfThree

자세한 문제는 여기를 참조하세요

 

이 문제는 array에서 3개를 뽑아 최고로 큰 값을 찾는 문제입니다.

 

우선 제가 작성한 code는 

fun solution(A: IntArray): Int {
       val size = A.size
    for (index in 1 until A.size) {

        val temp = A[index]
        var aux = index - 1

        while (aux >= 0 && A[aux] > temp) {

            A[aux + 1] = A[aux]
            aux--
        }
        A[aux + 1] = temp
    }

    var k_1  = A[0]*A[1]*A[size-1]
    var k_2 = A[size-1]*A[size-2]*A[size-3]
    
    if(k_1 > k_2){
        return k_1
    }else if(k_2 > k_1){
        return k_2
    }else{
        return k_2
    }
    
}

크기 순으로 정렬 후 제일 큰 3개를 곱한것과 제일 작은값2개 곱하기 제일큰 값을 비교 해서 더 큰 값을 반환하는 방법입니다. (제일 작은값 2개를 통한 계산은 음수도 들어가기 때문입니다.). 그리고 여기서는 삽입정렬을 사용했습니다.

 

결과는 77% 였습니다. 몇몇 경우에 TimeOut이 발생합니다. 아마 정렬이 문제인것 같습니다.

 

그래서 몇번 정렬 code를 수정하였습니다.

 

사실 수정했다고 하기보다. kotlin에서 제공하는 sort함수를 사용했습니다.(java에도 존재 합니다.) 이를 사용했더니 바로 100%가 되었고 코드도 더 간결해졌습니다.

 

fun solution(A: IntArray): Int {
    val size = A.size
    A.sort()

    var k_1  = A[0]*A[1]*A[size-1]
    var k_2 = A[size-1]*A[size-2]*A[size-3]
    
    if(k_1 > k_2){
        return k_1
    }else if(k_2 > k_1){
        return k_2
    }else{
        return k_2
    }
    
}

sort() 함수를 한번 분석해봐야곘습니다.

 

java doc에 있는 sort 함수를 확인해보았습니다. (원문은 여기서)

읽어보니 Timsort라고 Tim Peters라는 사람이 만든 sort 알고리즘을 가져와서 사용하는 것으로 파악되었습니다.

이 Timsort는  hybrid stable sorting algorithm으로  merge sort(합병 정렬) 와 insertion sort(삽입 정렬)을 합쳐놓은 알고리즘으로 데이터가 램덤하게 흩어진 형태 보다는, 대략 정렬된 상태로 있다는 것에 기반하여 디자인된 알고리즘 입니다.

 

다음에 좀더 자세히 java의 sort에 대하여 설명하겠습니다.