[Algorithm] Programmers_파일명 정렬 in Java

하이초·2024년 2월 20일

Java algorithm programmers

Algorithm

목록 보기

82/94

💡 Programmers Lv2. 순위 검색:

Compare를 오버라이딩하여 정렬하기

🌱 코드 in Java

알고리즘: BruteForce(?)

import java.util.*;

class Solution {
    public String[] solution(String[] files) {
         Arrays.sort(files, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int s1_i = -1, s2_i = -1;
                while (!(0 <= s1.charAt(++s1_i) - '0' && s1.charAt(s1_i) - '0' <= 9)); // head 길이 탐색
                while (!(0 <= s2.charAt(++s2_i) - '0' && s2.charAt(s2_i) - '0' <= 9));
                
                String head1 = s1.substring(0, s1_i).toLowerCase(); // head substring으로 잘라내고 소문자 치환
                String head2 = s2.substring(0, s2_i).toLowerCase();
                
                if (!head1.equals(head2)) // 문자열이 같지 않을 경우
                    return head1.compareTo(head2); // 문자열로 순위 비교
                
                int s1_j = s1_i, s2_j = s2_i;
                while (s1_j < s1.length() && (0 <= s1.charAt(s1_j) - '0' && s1.charAt(s1_j++) - '0' <= 9)); // number 길이 탐색
                while (s2_j < s2.length() && (0 <= s2.charAt(s2_j) - '0' && s2.charAt(s2_j++) - '0' <= 9));
                
                int num1 = Integer.parseInt(s1.substring(s1_i, s1_j)); // num int 치환
                int num2 = Integer.parseInt(s2.substring(s2_i, s2_j));

                return num1 - num2; // 숫자로 순위 비교
            }
        });
        return files;   
    }
}

이번 문제는 사실 처음에 compare를 오버라이딩 하지 않고 FileName이라는 클래스를 하나 만들어서 리스트를 만드는 방법을 택했었다.

class Solution {
    static class FileName {
        String head;
        int num;
        int idx;

        public FileName(String head, int num, int idx) {
            this.head = head;
            this.num = num;
            this.idx = idx;
        }

        public int getIdx() {
            return this.idx;
        }
    }
    
    public String[] solution(String[] files) {

        String[] answer = new String[files.length];
        List<FileName> tmp = new ArrayList<>();
        for (int i = 0; i < files.length; i++) {
            int j = -1;
            while (!(0 <= files[i].charAt(++j) - '0' && files[i].charAt(j) - '0' <= 9));
            int k = j;
            while (k < files[i].length() && (0 <= files[i].charAt(k) - '0' && files[i].charAt(k++) - '0' <= 9));
            tmp.add(new FileName(files[i].substring(0, j).toLowerCase(), Integer.parseInt(files[i].substring(j, k)), i));
        }
        Collections.sort(tmp, Comparator
                         .comparing((FileName o) -> o.head) // head로 정렬 후
						 .thenComparingInt(o -> o.num) // num으로 정렬 후
						 .thenComparingInt(o -> o.idx)); // 기존 idx로 정렬

        for (int i = 0; i < files.length; i++) {
            answer[i] = files[tmp.get(i).getIdx()]; // list에 정렬된 순서대로 원래 files idx에 접근
        }
        
        return answer;
    }
}

이런식으로. compare를 잘 활용할지 몰랐기 때문에 그냥 thenComparing 메소드를 써버린 것이다.
이런 경우엔 추가적으로 클래스 리스트 공간도 더 써야하고..
첫번째의 방법으로 푸는 것이 나은 것 같다.

그리고 첫번째 방법으로 풀면서 다른 분의 풀이를 보니

String head1 = s1.split("[0-9]")[0];

와 같은 식으로 정규식을 활용한 split도 보았다!
숫자를 구분자로 하여 문장을 split할 수 있다.

import java.util.*;
import java.util.regex.*;

class Solution {
    public String[] solution(String[] files) {
    	// 소문자 알파벳, 공백, 마침표, 대시가 1회 이상 반복되는 그룹과 1~5자리의 숫자 그룹으로 패턴 생성
        Pattern p = Pattern.compile("([a-z\\s.-]+)([0-9]{1,5})");

        Arrays.sort(files, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                Matcher m1 = p.matcher(s1.toLowerCase()); // 문자열 패턴 매칭
                Matcher m2 = p.matcher(s2.toLowerCase());
                m1.find();
                m2.find();

                if(!m1.group(1).equals(m2.group(1))) { // group(1) == head
                    return m1.group(1).compareTo(m2.group(1));
                } else {
                    return Integer.parseInt(m1.group(2)) - Integer.parseInt(m2.group(2)); // group(2) == number
                }
            }
        });

        return files;
    }
}