[프로그래머스] Lv.2 : [3차] 파일명 정렬 - 자바[Java]

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

프로그래머스

풀이

정렬 기준

1. HEAD: 문자 사전 순, 대소문자 구분X

2. NUMBER: 숫자 오름차순, 012 = 12

3. HEAD, NUMBER 같으면 입력 순서 그대로 유지 -> 안정 정렬

 

n <= 1000이므로 시간복잡도가 O(N^2)이어도 괜찮으며, 안정 정렬을 사용해야하므로 버블 소트를 사용하였다.

안정 정렬: 머지 소트, 버블 소트, 삽입 정렬
안정 정렬X: 퀵 소트

코드

class Solution {
    public String[] solution(String[] files) {
        int n = files.length;
        // 버블 소트
        for (int i = n-1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (isChange(files[j], files[j+1])) {
                    String tmp1 = files[j];
                    files[j] = files[j+1];
                    files[j+1] = tmp1;
                }
            }
        }
        
        return files;
    }
    
    static boolean isChange(String prev, String next) {
        // head 비교
        String head1 = getHead(prev);
        String head2 = getHead(next);
        
        int result = head1.compareToIgnoreCase(head2);
        if (result > 0) return true;
        else if (result < 0) return false;
        
        // head 부분이 같으면 number 비교
        int num1 = getNumber(head1, prev);
        int num2 = getNumber(head2, next);
        
        if (num1 > num2) return true;
        else return false;
    }
    
    static String getHead(String str) {
        int i = 0;
        for (; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                break;
            }
        }
        
        return str.substring(0, i);
    }
    
    static int getNumber(String head, String str) {
        int index = str.indexOf(head);
        index += head.length();
        int i = index;
        for (; i < str.length(); i++) {
            if (str.charAt(i) < '0' || str.charAt(i) > '9') {
                break;
            }
        }
        
        return Integer.parseInt(str.substring(index, i));
    }
}

str.compareToIgnoreCase(str2) 메서드를 사용하여 대소문자 구분 없이 문자열을 비교하였다.
다음과 같은 방법도 사용가능하다.
str.toUpperCase() -> str.compareTo(str2)

 

다른 풀이

블로그 링크

import java.util.*;

class Solution {
	public String[] solution(String[] files) {
    		Arrays.sort(files, new Comparator<String>() {
			@Override
			public int compare(String s1, String s2) {
				String[] file1 = detach(s1);
				String[] file2 = detach(s2);
				
				int headValue = file1[0].compareTo(file2[0]);
				
				if(headValue == 0) {
					int num1 = Integer.parseInt(file1[1]);
					int num2 = Integer.parseInt(file2[1]);
					
					return num1 - num2;
				} else {
					return headValue;
				}
			}
			
			private String[] detach(String str) {
				String head = "";
				String number = "";
				String tail = "";

				int idx = 0;
				for( ; idx < str.length() ; ++idx) {
					char ch = str.charAt(idx);
					if(ch >= '0' && ch <= '9') break;
					head += ch;
				}
				
				for( ; idx < str.length() ; ++idx) {
					char ch = str.charAt(idx);
					if(!(ch >= '0' && ch <= '9')) break;
					number += ch;
				}
				
				for( ; idx < str.length() ; ++idx) {
					char ch = str.charAt(idx);
					tail += ch;
				}
				
				String[] file = {head.toLowerCase(), number, tail};
				
				return file;
			}
		});
		return files;
	}
}

 

 

카카오 신입 공채 3차 해설