[JAVA] 바코드 정렬하기 by using Radix sort (기수정렬)

 

오늘은 Exercise 3에 있는 코딩 문제에 대한 포스팅이다. Exercise 2에는 시간 복잡도를 계산하는 문제가 많았고, 코딩 문제 또한 그전에 구현해놓은 것들을 불러와서 사용하는 게 많았기 때문에 다 스킵을 하였다. 

 

문제부터 다시 보자면

 

A barcode can be used to uniquely identify products. In the current avariant, a GIN-13 code is applied, where each code number consists of 13 digits 

이번 문제는 GTIN-13이란 바코드 번호를 소개하며 고정 13자리의 숫자열에 대해서 강조를 하고 있다.

 

a) The class product is given with attributes for the product name, GTIN-13 code number, and price. Implement a method

public static void gtinSort(Product [] plist),

which sorts an array of products in ascending order according to the GTIN-13 code number by menas of radixsort.

 

a문제에서는 주어진 13자리의 숫자열을 gtinSort라는 메소드를 이용해서 ascending order 즉 오름차순으로 정렬을 하라는 문제이다. 

그다음 b와 c의 문제는 구현한 배열의 시간 복잡도와 테스트 케이스를 이용해서 올바르게 작동되는지를 확인하라는 문제이다.

고로 a문제만 제대로 풀면 다음 두 문제는 무리없이 풀 수 있을 것이다.

 

이 문제를 풀기에 앞서 우리는 Radixsort라는게 무엇인지를 알아야 한다. 한국어로는 기수 정렬이라고 불리는 Radixsort는 낮은 자릿수부터 비교해 가면서 정렬을 해가는 정렬법이다. 단 조건이 있는데 자릿수가 고정되어야 한다는 것이다. 고정이라는 뜻이 무조건 2자리 정수 혹은 3자리 정수가 아니라 데이터의 자릿수가 최대 4자리 정수처럼 고정이 되어 있어야 한다. 

이 문제에서는 13자리 정수열을 비교하는 것이니 사용하기에 최고의 정렬이라 볼 수 있다.

 

시간 복잡도는 O(dn)으로 d는 가장 큰 데이터의 자리수 이다. 

 

기수 정렬을 이해할 때는 바구니를 생각하면 쉽다. 

 

0	1	2	3	4	5	6	7	8	9

 

이렇게 0~9라는 이름의 바구니가 있다고 생각을 해보자. 그리고 우리에게는 무작위의 정수열 [2,4,48,79,28,35,91,66,73]이 존재한다. 

 

예시는 최대크기의 정수의 자릿수가 2자리이니 우리는 총 두 번의 비교를 통해서 이 정수열을 정리할 수 있다.

 

먼저 주어진 정수열의 1의자리를 기준으로 해당하는 바구니에 각각의 원소들을 넣는다. 그럼

 

0	1	2	3	4	5	6	7	8	9
	91	2	73	4	35	66		28,48	79

 

위와 같이 들어가게 된다. 

 

그럼 [91,2,73,4,35,66,28,48,79] 와 같이 정렬이 된다. 여기서 두 번째 자리 즉 십의 자리를 기준으로 정렬을 한번 더 해준다. 

 

0	1	2	3	4	5	6	7	8	9
2,4		28	35	48		66	73,79		91

이렇게 정렬된 데이터를 꺼내면 [2,4,28,35,48,66,73,79,91] 로 정렬이 된다. 문제에서 오름차순으로 정렬을 하라고 했으니 정렬이 완료가 된 것이다.

 

그럼 다시 문제로 들어가서 주어진 템플릿을 확인해 봐야한다.

 

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

public class Product implements Comparable 
{
private String name;
private int price;
private String gtin13; //key = 13 digit GTIN number

public static final int GTIN_LENGTH = 13;

public Product(String name, int price, String gtin) {
this.name = name;
this.price = price;
this.gtin13 = gtin;
}

public String getGtin13() {
return gtin13;
}

public String toString() {
int euro = price / 100;
int cent = price % 100;
String preisStr = euro + "," + String.format("%02d", cent);
return name + ", GTIN-13 " + gtin13  + ", price: " + preisStr + " EUR";
}

public static void gtinSort(Product[] alist) {
//TODO
//TODO
//TODO
//TODO
//TODO
//TODO
//TODO
//TODO
//TODO
//TODO
//TODO
}




@Override
public int compareTo(Product other) {
return gtin13.compareTo(other.gtin13);
}


/** generates randomly an array containing the specified number of products */
public static Product[] generateProductList(int number) {
Product[] aliste = new Product[number];

Random rand = new Random();

for (int i = 0; i < aliste.length; i++) {
String name = "Article_" + i;
// int price = rand.nextInt(1000);
int price = i;

//generate GTIN randomly
String ean = "";
for (int pos = 0; pos < GTIN_LENGTH; pos++) {
ean += rand.nextInt(10);
}

aliste[i] = new Product(name, price, ean);
}

return aliste;
}

}

밑에는 GtinSortMeasurement.java이다. 

import java.util.Arrays;

public class GtinSortMeasurement {

	public static final int MIN_N = 10;
	public static final int MAX_N = 1000000;
	
	/** Measure runtime of sorting lists of products using radixsort and standard Java sort. */
	public static void main(String[] args) {
		for (int n = MIN_N; n <= MAX_N; n *= 10) {
			measureSort(n);
		}
		
		System.out.println("--- done ---");

	}
	
	public static void measureSort(int n) {
		System.out.printf("generate n = %10d products. ", n);
		
		// product list used for radixsort
		Product[] alist1 = Product.generateProductList(n);
		
		// copy of product list, used for Arrays.sort
		Product[] alist2 = alist1.clone();

		System.out.print("gtinSort(): ");
		long start1 = System.nanoTime();
		Product.gtinSort(alist1);
		long end1 = System.nanoTime();
		double time1ms = (end1 - start1)/10e6;
		System.out.printf("%8.2f ms ", time1ms);
		
		
		System.out.print("| Arrays.sort(): ");
		long start2 = System.nanoTime();
		Arrays.sort(alist2);
		long end2 = System.nanoTime();
		double time2ms = (end2 - start2)/10e6;
		System.out.printf("%8.2f ms %n", time2ms);
		
	}

}

이제 여기서 기수 정렬을 구현을 해줘야 하는데 

 

생각한 방식은 정수의 자릿수는 13으로 고정이 되어있으니 자리수 비교는 13번만 하면 되고... 문제는 각각의 자릿수를 어떻게 확인하냐 였다.. ㅠㅠ 이리저리 찾아보다가 자리수를 줄이는(?) 방식이 보였다. 우리는 13자리의 정수를 한 번씩 다 비교해서 바구니에 넣어 줘야 한다. 그러기 위해선 나머지 연산과 나눗셈 연산을 적절히 활용해야 하는데, 1의 자리의 정수를 확인하는 방법은 쉽다. 예를 들어 97이라는 수가 있으면 97을 10으로 나눈 나머지가 결국 1의 자리가 되기 때문이다. 문제는 그 다음 십의자리+ 이다. 예를들어 341이라는 숫자가 있고 1의 자리는 아까처럼 10으로 나눈 나머지라고 하면 1이 나오기 때문에 문제가 없지만 100으로 나눈 나머지는 41이다.. 근데 여기서 나머지 연산이 아닌 나눗셈 연산을 해서 몫을 찾으면 어떨까? 41을 10으로 나누면 4이다. 그렇다 1의 자리는 나머지 연산으로 구하고 그 이후는 나눗셈 연산을 통해서 몫을 구하면 되는 것이다. 그래서 나머지 연산은 10부터 시작하고 나눗셈 연산은 1부터 시작해서 한번 돌아갈 때마다 10씩 증가하면 되는 것이다.

 

 public static void gtinSort(Product[] alist) {
	      
	     long mod = 10;
	     long dev = 1;
	      
	      for (int i = 0; i < GTIN_LENGTH; i++, dev *= 10, mod *= 10) {
	         
	         for (int j = 0; j < alist.length; j++) {
	           long gtin13 = Long.parseLong(alist[j].getGtin13());
	            int bucket = (int) ((gtin13 % mod) / dev);
	            counter[bucket].add(alist[j]);
	         }
	         
	         int pos = 0;
	         
	         for(int j = 0; j < counter.length; j++) {
	            Product nlist;
	            while((nlist = counter[j].poll()) != null) {
	               alist[pos++] = nlist;
	            }
	         }
	      }
	   }

그렇게 해서 탄생한 코드이다 첫 번째 반복문은 나머지 연산과 나눗셈 연산의 값들을 10씩 곱해주는 것이고 두 번째 반복문은 자릿수를 기준으로 바구니에 넣는 연산을 한다. 3번째 반복문 에선 counter라는 바구니에 담긴 원소들을 다시 alist로 돌려놓는 연산이다. 

 

이렇게 하면 alist에 오름차순으로 정렬된 13자리의 바코드 값이 나온다.

 

 

이렇게 해서 10부터 1000000까지의 경우의 수에 대해서 테스트를 하라는 문제의 결과 값이다.