[문제풀이] 파일명정렬

업데이트:

2018 Kakao Blind Recruitment 기출 문제

문제 링크 : 파일명정렬

풀이 시간 : 60분

1. 문제 풀이

파일들의 이름들을 특정 규칙으로 정렬하는 문제

파일의 이름을 처음 숫자가 나오기 전까지의 문자열(Head)과 처음 숫자(Number), 나머지(Tail) 나누고 Head와 Number만 가지고 정렬을 한다.

정렬을 위해서 merge sort를 사용

1) merge sort를 사용

2) 비교 시 먼저 파일명을 Head와 Number로 나눔 (Tail은 정렬에 영향을 안주기 때문에 버림)

3) Head 먼저 비교 후 같을 경우 Number 비교

2. 주의

정렬 조건 1) 대소문자 구별 X 2) 숫자 앞에 0이 올 수 있다 ex) 010 -> 10으로 계산 3) Head와 Number 값이 같으면 먼저 들어온 순서로 정렬

3) 조건 때문에 stable 정렬을 해야 한다 (merge 정렬 사용한 이유)

3. 소스 코드

```java static public String[] solution(String[] files) { merge( files, 0, files.length - 1); return files; }

static public void merge(String[] files, int start, int end) {
	if (start >= end) {
		return;
	} else {
		String[] answer = new String[end-start+1];
		int mid = (start + end) / 2;
		// 왼쪽 부분
		merge(files, start, mid);
		// 오른쪽 부분
		merge(files, mid + 1, end);
		int left_pivot = start;
		int right_pivot = mid + 1;
		int pivot = 0;
		while (left_pivot != mid + 1 && right_pivot != end + 1) {
			// 각 파일명 비교,	true면 왼쪽, false면 오른쪽
			if (comp(files[left_pivot], files[right_pivot])) {
				answer[pivot] = files[left_pivot];
				left_pivot++;
			} else {
				answer[pivot] = files[right_pivot];
				right_pivot++;
			}
			pivot++;
		}
		// 나머지 파일명들 이동
		if (left_pivot == mid + 1) {
			for (int i = right_pivot; i <= end; i++) {
				answer[pivot] = files[i];
				pivot++;
			}
		} else if (right_pivot == end + 1) {
			for (int i = left_pivot; i <= mid; i++) {
				answer[pivot] = files[i];
				pivot++;
			}
		}
		int j = start;
		// 파일명 배열에 옮김
		for (int i = 0; i < answer.length; i++) {
			files[j] = answer[i];
			j++;
		}
	}
}

static boolean comp(String left, String right) {
	String[] left_arr = conv(left);
	String[] right_arr = conv(right);
	// 대소문자 구별하지 않으므로 compareToIgnoreCase 사용
	int head = left_arr[0].compareToIgnoreCase(right_arr[0]);
	if (head <0) {
		return true;
	} else if (head == 0) {
		int number_l = Integer.parseInt(left_arr[1]);
		int number_r = Integer.parseInt(right_arr[1]);
		// 같을 경우 들어온 순서 있므로 왼쪽이 먼저
		if (number_l <= number_r) {
			return true;
		} else {
			return false;
		}
	} else {
		return false;
	}
}

// head와 number로 분리
static String[] conv(String s) {
	// 인덱스 0이 head 부분, 1이 number,  tail은 정렬에 필요 없으므로 버림
	String[] result = new String[2];
	for (int i = 0; i < s.length(); i++) {
		// 숫자 찾기
		if ('0' <= s.charAt(i) && s.charAt(i) <= '9') {
			// 찾으면 그 전까지는 head 부분
			result[0] = s.substring(0, i);
			boolean flag = true;
			// 숫자가 아닐 때까지 찾기
			for (int j = i + 1; j < s.length(); j++) {
				if (!('0' <= s.charAt(j) && s.charAt(j) <= '9')) {
					// 찾으면 head 부분 이후 부터 현재 인덱스까지는 number 부분
					result[1] = s.substring(i, j);
					flag = false;
					break;
				}
			}
			// 파일명 끝까지 숫자 일때
			if (flag) {
				result[1] = s.substring(i, s.length());
			}
			break;
		}
	}
	return result;
}
```

4. 개선 사항

파일명에 대한 객체를 만들어서 head와 number부분을 미리 저장

지금은 파일명 비교시 head와 number 계속 찾기 때문에 미리 구해 놓으면 성능이 좋아질 것이라고 생각

5. 후기

오랜만에 merge sort를 직접 구현해봤다.

또한 처음에 Head와 Number가 같으면 Tail로 비교 해야는지

문제를 제대로 읽었다면 좀 더 빠르게 풀었을듯

참고