파일명 정렬

문제

파일명을 주어진 기준에 따라 정렬하는 프로그램을 작성하는 문제입니다. 파일명은 영문자, 숫자, 공백, 마침표, 빼기 부호로만 이루어져 있으며 크게 세 부분(HEAD, NUMBER, TAIL)으로 나뉩니다.

• HEAD: 숫자가 아닌 문자로 이루어져 있으며, 최소 한 글자 이상입니다.
• NUMBER: 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있습니다. (0~99999)
• TAIL: NUMBER 이후의 나머지 모든 부분입니다. (비어있을 수 있습니다.)

정렬 기준은 다음과 같습니다.

1. HEAD 기준 사전순 정렬: 대소문자를 구분하지 않습니다. (예: muzi == MUZI)
2. NUMBER 기준 오름차순 정렬: HEAD가 같을 경우, 숫자 값(정수)을 기준으로 오름차순 정렬합니다. (예: 012 == 12)
3. 입력 순서 유지 (Stable Sort): HEAD와 NUMBER가 모두 같을 경우, 원래 입력에 주어진 순서를 유지합니다.

• 입력: 파일명 배열 files (길이 1,000 이하)
• 출력: 정렬된 파일명 배열 반환

링크: https://school.programmers.co.kr/learn/courses/30/lessons/17686

풀이: 순차 탐색을 통한 파싱과 Stable Sort

자바의 Arrays.sort()는 객체 배열에 대해 Stable Sort(안정 정렬)를 보장하므로, 비교 기준을 명시하는 커스텀 Comparator만 잘 구현하면 쉽게 해결할 수 있습니다. 가장 까다로운 부분은 문자열을 세 부분으로 오차 없이 나누는 것입니다.

• 순차적 파싱: 인덱스(idx)를 통해 문자열의 처음부터 순차적으로 탐색합니다.
  1. 숫자가 나오기 전까지 인덱스를 증가시켜 HEAD를 분리합니다.
  2. 숫자가 끝날 때까지 인덱스를 증가시켜 NUMBER를 분리합니다.
  3. 남은 문자열 전부를 TAIL로 지정합니다.
• 비교 (Comparator): 분리된 배열에서 HEAD를 모두 대문자로 변환(toUpperCase())하여 문자열 비교(compareTo)를 수행합니다. HEAD가 같다면, NUMBER 부분을 Integer.parseInt()를 통해 정수로 변환하여 오름차순으로 정렬합니다. 두 값이 모두 같을 경우 0을 반환하여 기존 순서를 유지하도록 합니다.

코드

import java.util.*;

class Solution {
    public String[] solution(String[] files) {
        Arrays.sort(files, (f1, f2) -> {
            String[] f1Parts = split(f1);
            String[] f2Parts = split(f2);
            
            String f1Head = f1Parts[0].toUpperCase();
            String f2Head = f2Parts[0].toUpperCase();
            
            // 1. HEAD 비교 (대소문자 무시)
            if (f1Head.equals(f2Head)) {
                // 2. HEAD가 같으면 NUMBER를 정수로 변환하여 비교
                int f1Num = Integer.parseInt(f1Parts[1]);
                int f2Num = Integer.parseInt(f2Parts[1]);
                
                return Integer.compare(f1Num, f2Num);
            }
            
            return f1Head.compareTo(f2Head);
        });
        
        return files;      
    }
    
    // 파일명을 HEAD, NUMBER, TAIL 3부분으로 분리하는 메서드
    String[] split(String s) {
        int idx = 0;
        
        // 1. HEAD 추출 (숫자가 나오기 전까지)
        while (idx < s.length() && !Character.isDigit(s.charAt(idx))) {
            idx++;
        }
        String head = s.substring(0, idx);
        
        // 2. NUMBER 추출 (이후 연속된 숫자)
        int startNum = idx;
        while (idx < s.length() && Character.isDigit(s.charAt(idx))) {
            idx++;
        }
        String number = s.substring(startNum, idx);
        
        // 3. TAIL 추출 (나머지 전부)
        String tail = s.substring(idx);
        
        return new String[]{head, number, tail};
    }
}

알고리즘 분류

구현 (Implementation), 문자열 (String), 정렬 (Sorting)