160929.md

알고리즘 정리

1. Permutation - 순열

주어진 수 에서 중복되지 않는 경우의 모든 수를 얻는 Permutation(순열)의 예 이다.
예를 들어 [1, 2, 3]의 경우 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]을 얻을 것 이다.

1.1 Collection의 List를 이용한 해결 방법.

public ArrayList<ArrayList<Integer>> permute(int[] num) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 
	//start from an empty list
	result.add(new ArrayList<Integer>());
 
	for (int i = 0; i < num.length; i++) {
		//list of list in current iteration of the array num
		ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>();
 
		for (ArrayList<Integer> l : result) {
			// # of locations to insert is largest index + 1
			for (int j = 0; j < l.size()+1; j++) {
				// + add num[i] to different locations
				l.add(j, num[i]);
 
				ArrayList<Integer> temp = new ArrayList<Integer>(l);
				current.add(temp);
				
        // - remove num[i] add
				l.remove(j);
			}
		} 
		result = new ArrayList<ArrayList<Integer>>(current);
	} 
	return result;
}  

1.2. 재귀를 이용한 해결 방법.

public ArrayList<ArrayList<Integer>> permute(int[] num) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	permute(num, 0, result);
	return result;
}
 
void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result) {
	if (start >= num.length) {
		ArrayList<Integer> item = convertArrayToList(num);
		result.add(item);
	}
	for (int j = start; j <= num.length - 1; j++) {
		swap(num, start, j);
		permute(num, start + 1, result);
		swap(num, start, j);
	}
}
 
private ArrayList<Integer> convertArrayToList(int[] num) {
	ArrayList<Integer> item = new ArrayList<Integer>();
	for (int h = 0; h < num.length; h++) {
		item.add(num[h]);
	}
	return item;
}
 
private void swap(int[] a, int i, int j) {
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

2. atoi 함수

C/C++에서 atoi함수에서는 다음과 같은 역할을 한다.

• 입력된 문자열 조합이 숫자인지 판단한 뒤 숫자일 경우 숫자로 변환해서 반환한다. (Integer)

atoi함수의 역할을 제대로 수행하기 위해서는 다음과 같은 조건들이 필요 하다.

1. 입력된 문자열이 null이나 empty string이 아니다.
2. 입력된 문자열내부에 공백이 있으면 안된다.
3. 최초 글자가 +/- 이거나 숫자이어야 한다.

구현되어진 내용중 가장 중요한 부분은 다음과 같다.

 double result = 0;

	while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
		result = result * 10 + (str.charAt(i) - '0');
		i++;
	}

반복문 내부에서 입력된 모든 문자들을 순회하면서 해당하는 숫자로 알려진 문자 캐릭터를 숫자로 변환하는 과정이다.

정리된 구현 내용은 다음과 같다.

public int atoi(String str) {
	if (str == null || str.length() < 1)
		return 0;
 
	// trim white spaces
	str = str.trim();
 
	char flag = '+';
 
	// check negative or positive
	int i = 0;
	if (str.charAt(0) == '-') {
		flag = '-';
		i++;
	} else if (str.charAt(0) == '+') {
		i++;
	}
	// use double to store result
	double result = 0;
 
	// calculate value
	while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
		result = result * 10 + (str.charAt(i) - '0');
		i++;
	}
 
	if (flag == '-')
		result = -result;
 
	// handle max and min
	if (result > Integer.MAX_VALUE)
		return Integer.MAX_VALUE;
 
	if (result < Integer.MIN_VALUE)
		return Integer.MIN_VALUE;
 
	return (int) result;
}