파일명 정렬
문제정의
파일명 정렬 알고리즘을 짜는 문제이다 자세한 문제 설명은 아래 링크를 참고하도록 하자.
문제 링크
문제풀이
전체 코드는 다음과 같다. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
public class SortFileName {
//프로그래머스 level2 파일명 정렬
public static void main(String[] args) {
String[] files = {
"img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"
};
HashMap<String, Integer> order_map = new HashMap<>();
HashMap<String, Integer> head_map = new HashMap<>();
HashMap<Integer, Integer> num_map = new HashMap<>();
String[] head_arr = new String[files.length];
int[] num_arr = new int[files.length];
int i = 0;
for(String file : files)
{
order_map.put(file, i);
String[] arr = ReturnHeadNumber(file);
head_arr[i] = arr[0].toLowerCase();
int number = Integer.parseInt(arr[1]);
num_arr[i++] = number;
}
Arrays.sort(head_arr);
for(String s : head_arr)
head_map.put(s, head_map.getOrDefault(s, head_map.size()));
Arrays.sort(num_arr);
for(int s: num_arr)
num_map.put(s, num_map.getOrDefault(s, num_map.size()));
Arrays.sort(files, new Comparator<String>(){
public int compare(String o1, String o2)
{
String[] o1_arr = ReturnHeadNumber(o1);
String[] o2_arr = ReturnHeadNumber(o2);
if(head_map.get(o1_arr[0]) < head_map.get(o2_arr[0]))
return -1;
else if(head_map.get(o1_arr[0]) > head_map.get(o2_arr[0]))
return 1;
else
{
if(num_map.get(Integer.parseInt(o1_arr[1]))
< num_map.get(Integer.parseInt(o2_arr[1])))
return -1;
else if(num_map.get(Integer.parseInt(o1_arr[1]))
> num_map.get(Integer.parseInt(o2_arr[1])))
return 1;
else
{
return order_map.get(o1) - order_map.get(o2);
}
}
}
});
}
public static String[] ReturnHeadNumber(String s)
{
String[] res = new String[2];
int head_idx = 0;
int tail_idx = s.length();
int idx = 0;
boolean isnum = false;
for(char c : s.toCharArray())
{
if((c >= '0') && (c <= '9') && (!isnum))
{
isnum = true;
head_idx = idx;
}
if(isnum)
{
if((c < '0') || (c > '9'))
{
tail_idx = idx;
break;
}
}
idx++;
}
String head = s.substring(0, head_idx).toLowerCase();
String number = s.substring(head_idx, tail_idx);
res[0] = head;
res[1] = number;
return res;
}
}
22번째 줄에서 순서 사전을 만드는 것을 볼 수 있다 들어온 파일명대로 순서대로 i를 증가하며 저장한다. 이와 동시에 head사전과 number사전을 만들기 위한 준비를 한다. 정렬은 하지 않은 채 배열에 넣는다. 이때 head는 모두 소문자로 바꾸어 넣고 number는 모두 int로 변환하여 넣는다.
이제 head를 정렬한다. 정렬하고 이를 사전에 넣어야하는데, 만약 사전에 이미 있는 경우라면 값을 바꾸면 안되기 때문에 getOrDefault함수를 활용하였다. 사전에 없는 경우라면 사전의 크기를 값으로 지정한다. number또한 똑같은 원리로 한다. 이제 모든 사전이 완성되었다.
파일들을 정렬하기 위해 비교자를 새로 정의하였다. 비교자 선언은 어렵지 않다. 아까 말한 우선순위를 그대로 코드에 적었으니 찬찬히 보면 이해가 갈 것이다. ReturnHeadNumber에서 head와 number값을 받아올 수 있다.
ReturnHeadNumber를 보자. head_idx와 tail_idx가 있다. head_idx에는 head가 끝나는 인덱스를 너흘 것이고 tail_idx는 tail이 시작되는 지점을 넣을 것이다. isnum은 flag인데 코드를 살펴보면서 설명하겠다. 일단 문자열에서 문자를 하나씩 떼와서 처음으로 숫자가 나올 경우 이곳부터 number가 시작되므로 head_idx에 해당 인덱스 값을 넣고 isnum을 true로 해준다. isnum이 없다면 숫자가 여러자리 일 때도 head_idx가 계속 증가하기 때문이다.
isnum이 true로 바뀌면 이제 tail값을 찾아야한다. 처음으로 숫자가 아닌 구간이 나온다면 그곳부터는 tail이므로 tail_idx에 해당 idx를 넣고 반복문을 탈출한다. 이제 두 값으로 문자열을 잘라주면 우리가 원하는 head와 number를 가져올 수 있다.
최종 시간복잡도는 파일들의 개수를 n개라 할 때, \(O(nlogn)\)이다.
테스트
비교자를 새로하는 부분에서 테스트케이스가 많으면 간혹 논리가 맞아도 정렬이 꼬이는 경우가 있어서 불안했었는데, 무사히 통과해서 다행이다.