CodingBat Java: Logic-2 (evenlySpaced)

problem - Given three ints, a b c, one of them is small, one is medium and one is large. Return true if the three values are evenly spaced, so the difference between small and medium is the same as the difference between medium and large.

 

evenlySpaced(2, 4, 6) → true
evenlySpaced(4, 6, 2) → true
evenlySpaced(4, 6, 3) → false

 

 

---

Solution

이번 문제는 하나는 가장 작고, 하나는 중간값, 하나는 가장 큰 값으로 구성된 3개의 숫자가 주어진다. 그리고 return 값으로는 작은 값과 중간값의 차이와 중간값과 가장 큰 값의 차이가 같으면 true를 반환하는것이 문제이다.

 

이 문제를 풀기 위해서 생각한 방법은 들어오는 3개의 값은 랜덤이기 때문에 이를 오름차순으로 정렬하는 방법이다.

Array.sort 함수를 사용하여 임의의 배열에 랜덤값 3개를 넣고 정렬하면 0번째 인덱스는 가장 작은값이 되고, 2번째 인덱스는 가장 큰 값이 되기 때문에 정렬한 뒤 차이를 계산해 답을 구했다.

 

---

 

Code

---

Arrays.sort

이번에 사용한 함수에 대한 정리이다.

 

이 sort 함수에서 사용된 알고리즘은 Dual-Pivot Quicksort이다. 이 알고리즘에 대해 알아보기 전에 먼저 Quicksort에 대해 알아볼 필요가 있다고 생각한다.

 

퀵 정렬 (Quick sort)

• 분할 정복 알고리즘(divide and conquer)방법으로, 이는 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

과정은 다음과 같다.

1. 리스트 안에 있는 요소를 선택하고, 이렇게 고른 원소를 피벗(pivot)이라고 한다.

2. 피벗을 기준으로 피벗보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 정렬한다.

3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.

  • 분할한 리스트에서 대해 순환 호출 을 이용하여 정렬을 반복한다.

  • 분할한 리스트에 대해서도 1-2번 과정을 반복한다.

4. 부분 리스트들의 크기가 0이나 1이 될 때 까지 반복한다.

 

quicksort example

이렇게 진행될 경우 시간복잡도는 O(NlogN)으로 평균적으로 빠르다고 알려저 있다. 여기에서 이 장점을 높여보고자, 피벗을 여러 개 선정해보는 방법을 고안해보았고, 일반적인 quicksort보다 좋은 성능을 보여주기 시작한 방법이 Vladimir Yaroslavskiy의 dual-pivot quicksort이다.

 

 

dual-pivot quicksort의 flow에 대해 알아보자.

과정은 다음과 같다.

1. 배열의 가장 왼쪽 항목은 left pivot, 가장 오른쪽 항목은 right pivot으로 지정하고, lp가 rp보다 클 경우 두 값을 switch한다.

2. 두 pivot을 기준으로하여 lp보다 작은 (1)영역, lp와 rp의 중간인 (2)영역, rp보다 큰 (3)영역으로 나뉜다.

3. 이후 3개의 영역에 대해 순환 호출 을 진행하여 dual-pivot quicksort를 진행한다.

 

이렇게 동작하는 dual-pivot quicksort는 보통의 퀵소트보다 좋은 성능을 나타내는 것으로 판명되어 Arrays.sort 함수에 사용된다.

---

 

 

Impressive Code

이 코드가 인상깊었던 이유는 정렬된 함수를 사용할 필요 없이 3가지의 경우의 수를 간단하게 수학적으로 풀이한 점이었다.

3가지의 경우의 수로 나오는 이유는 isSpaced라는 함수의 세번째 인자인 c에 가장 큰 수가 오는 경우는 a,b,c가 올 수 있으므로 3가지이고, 비교하는 연산자가 다른 코드에 비해 적었기 때문에 좋은 코드라고 생각한다.

 

 

출처: https://blog.steamedu123.com/entry/티스토리-서식-글-쓰기 [모두의 블로그]

https://cs-vegemeal.tistory.com/53

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

http://www.javaproblems.com/2013/11/java-logic-2-evenlyspaced-codingbat.html