링크
문제 설명
문제 규칙
- 문자열은 알파벳 대소문자와 숫자로만 이루어져 있다.
- 숫자열이 알파벳보다 앞에 오고, 알파벳끼리는 AaBbCc...XxYyZz의 순서를 따른다.
- 문자열을 비교하는 중 숫자가 있을 경우 그 다음에 오는 숫자를 최대한 많이 묶어 한 단위로 비교한다. 예를 들어 "a12bc345"는 "a", "12", "b", "c", "345"의 다섯 단위로 이루어져 있다.
- 숫자열끼리는 십진법으로 읽어서 더 작은 것이 앞에 온다. 이때 예제 2에서와 같이 값이 263을 초과할 수 있다.
- 같은 값을 가지는 숫자열일 경우 앞에 따라붙는 0의 개수가 적은 것이 앞에 온다.
문제 풀이
주어진 규칙에 맞게 짜면 해결.
회고
- 처음에 문자열을 2차원 ArrayList에 저장해 char와 숫자를 저장해 계산에 용이하게 문제를 풀었었다. 하지만 시간이 오래 걸려 문자열 배열을 그대로 사용해 다시 한번 문제를 풀었다. 결과적으로 시간, 공간 복잡도가 내려갔다! 쉽고 익숙한 방법이 항상 정답은 아닌듯 하다.
- 문자열 배열을 사용해 문제를 풀던 과정에서 인덱스 문제 때문에 고생을 했었다. 탐색할 때 숫자일 경우 앞의 0을 세야하는데 그 과정에서 문자열의 총 길이를 초과할 수도 있기 때문에 아래와 같은 과정이 추가되어야 한다.
i = i >= len1 ? len1 : i; j = j >= len2 ? len2 : j;
2차원 ArrayList를 사용한 소스코드(느림)
public class Baek_20210_파일탐색기 {
static int N;
static String[] str;
static ArrayList<ArrayList<String>> al = new ArrayList<ArrayList<String>>();
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb;
N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i++) {
al.add(new ArrayList<>());
}
for(int i = 0; i < N; i++) {
String s = br.readLine();
for(int j = 0; j < s.length(); j++) {
sb = new StringBuilder();
if('0' <= s.charAt(j) && s.charAt(j)<= '9') {
while(j < s.length() && '0' <= s.charAt(j) && s.charAt(j)<= '9') {
sb.append(s.charAt(j++));
}
j--;
}else {
sb.append(s.charAt(j));
}
al.get(i).add(sb.toString());
}
}
Collections.sort(al, new Comparator<ArrayList<String>>() {
@Override
public int compare(ArrayList<String> o1, ArrayList<String> o2) {
int len1 = o1.size();
int len2 = o2.size();
int i = 0, j = 0;
for(; i < len1 && j < len2; i++, j++) {
if(o1.get(i).equals(o2.get(j)))
continue;
boolean numeric1 = isNum(o1.get(i));
boolean numeric2 = isNum(o2.get(j));
//둘다 숫자
if(numeric1 && numeric2) {
//숫자의 0 제거
String s1 = o1.get(i).replaceAll("^0+","");
String s2 = o2.get(j).replaceAll("^0+","");
//0을 제거 했으므로 길이가 긴 것이 더 큰 숫자
if(s1.length() > s2.length())
return 1;
if(s2.length() > s1.length())
return -1;
//길이가 같을 경우 한자리씩 비교하며 두 수 비교
for(int a = 0, b = 0; a<s1.length() && b < s2.length(); a++, b++) {
if(s1.charAt(a) > s2.charAt(b))
return 1;
else if (s1.charAt(a) < s2.charAt(b))
return -1;
}
//숫자까지 같다면 0의 갯수가 작은순
return o1.get(i).length() - o2.get(j).length();
}
//둘다 문자
if(!numeric1 && !numeric2) {
char c1 = o1.get(i).charAt(0);
char c2 = o2.get(j).charAt(0);
boolean isUpper1 = c1 - 'a' < 0 ? true : false;
boolean isUpper2 = c2 - 'a' < 0 ? true : false;
int n1 = c1 - 'a' >= 0 ? c1 - 'a' : c1 - 'A';
int n2 = c2 - 'a' >= 0 ? c2 - 'a' : c2 - 'A';
//둘다 대문자 이거나 둘다 소문자
if((isUpper1 && isUpper2) || (!isUpper1 && !isUpper2)) {
return n1 - n2;
}
//c1 소문자 && c2대문자
if(!isUpper1 && isUpper2) {
//c1,c2가 같은 문자일 경우
if(n1 == n2)
return 1;
//다른 문자일 경우
return n1 - n2;
}
//c1 대문자 && c2소문자
if(isUpper1 && !isUpper2) {
//c1,c2가 같은 문자일 경우
if(n1 == n2)
return -1;
//다른 문자일 경우
return n1 - n2;
}
}
//o1 문자, o2 숫자
if(!numeric1 && numeric2) {
return 1;
}
//o1 숫자, o2 문자
if(numeric1 && !numeric2) {
return -1;
}
}
//같은 문자인데 뒤에 다른 문자열이 붙는경우 더 깉 문자열이 뒤로
if(len1 != i) {
return 1;
}
if(len2 != j) {
return -1;
}
return 0;
}
});
sb = new StringBuilder();
for(int i = 0; i < al.size(); i++) {
StringBuilder sb2 = new StringBuilder();
for(String s : al.get(i)) {
sb2.append(s);
}
sb.append(sb2.toString()).append("\n");
}
bw.write(sb.toString());
bw.flush();
}
static boolean isNum(String s) {
if('0' <= s.charAt(0) && s.charAt(0) <= '9')
return true;
return false;
}
}
소스코드
public class Baek_20210_파일탐색기2 {
static int N;
static String[] str;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
str = new String[N];
for (int i = 0; i < N; i++) {
str[i] = br.readLine();
}
Arrays.sort(str, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
int i = 0, j = 0;
for (; i < len1 && j < len2; i++, j++) {
char c1 = s1.charAt(i);
char c2 = s2.charAt(j);
// 숫자인지 체크
boolean numeric1 = isNum(c1);
boolean numeric2 = isNum(c2);
// 둘다 숫자
if (numeric1 && numeric2) {
// 숫자 앞 0 갯수 세기
int cnt1 = 0, cnt2 = 0;
while (i < s1.length() && '0' == s1.charAt(i)) {
cnt1++;
i++;
}
while (j < s2.length() && '0' == s2.charAt(j)) {
cnt2++;
j++;
}
i = i >= len1 ? len1 : i;
j = j >= len2 ? len2 : j;
// 0을 제외한 숫자
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
while (i < s1.length() && '0' <= s1.charAt(i) && s1.charAt(i) <= '9') {
if ('0' <= s1.charAt(i) && s1.charAt(i) <= '9')
sb1.append(s1.charAt(i));
i++;
}
while (j < s2.length() && '0' <= s2.charAt(j) && s2.charAt(j) <= '9') {
if ('0' <= s2.charAt(j) && s2.charAt(j) <= '9')
sb2.append(s2.charAt(j));
j++;
}
i--;
j--;
// 0을 제거 했으므로 길이가 긴 것이 더 큰 숫자
if (sb1.length() > sb2.length())
return 1;
if (sb2.length() > sb1.length())
return -1;
// 길이가 같을 경우 한자리씩 비교하며 두 수 비교
String num1 = sb1.toString();
String num2 = sb2.toString();
for (int a = 0, b = 0; a < num1.length() && b < num2.length(); a++, b++) {
if (num1.charAt(a) > num2.charAt(b))
return 1;
else if (num1.charAt(a) < num2.charAt(b))
return -1;
}
// 숫자까지 같다면 0의 갯수가 작은순
if(cnt1 != cnt2)
return cnt1 - cnt2;
}
// 둘다 문자
if (!numeric1 && !numeric2) {
// 같은 캐릭터값이 경우 무시
c1 = s1.charAt(i);
c2 = s2.charAt(j);
if (c1 == c2)
continue;
boolean isUpper1 = c1 - 'a' < 0 ? true : false;
boolean isUpper2 = c2 - 'a' < 0 ? true : false;
int n1 = c1 - 'a' >= 0 ? c1 - 'a' : c1 - 'A';
int n2 = c2 - 'a' >= 0 ? c2 - 'a' : c2 - 'A';
// 둘다 대문자 이거나 둘다 소문자
if ((isUpper1 && isUpper2) || (!isUpper1 && !isUpper2)) {
return n1 - n2;
}
// c1 소문자 && c2대문자
if (!isUpper1 && isUpper2) {
// c1,c2가 같은 문자일 경우
if (n1 == n2)
return 1;
// 다른 문자일 경우
return n1 - n2;
}
// c1 대문자 && c2소문자
if (isUpper1 && !isUpper2) {
// c1,c2가 같은 문자일 경우
if (n1 == n2)
return -1;
// 다른 문자일 경우
return n1 - n2;
}
}
// o1 문자, o2 숫자
if (!numeric1 && numeric2) {
return 1;
}
// o1 숫자, o2 문자
if (numeric1 && !numeric2) {
return -1;
}
}
// 같은 문자인데 뒤에 다른 문자열이 붙는경우 더 깉 문자열이 뒤로
if (len1 != i) {
return 1;
}
if (len2 != j) {
return -1;
}
return 0;
}
});
for (String s : str) {
sb.append(s).append("\n");
}
bw.write(sb.toString());
bw.flush();
}
static boolean isNum(char c) {
if ('0' <= c && c <= '9')
return true;
return false;
}
}GITHUB
안녕하세요, 백엔드 개발에 관심이 많은 변지훈입니다.👋