P17686. 파일명 정렬

문제

제출 코드

• 사용 알고리즘 : 자료구조, 우선순위 큐, 정렬

파일을 HEAD, NUMBER, TAIL로 구분하고 주어진 정렬조건에 맞게 정렬하면 되는 문제.

정렬문제를 만날 때마다 여러가지 방법으로 정렬 해봤는데, 문제에서 주어진 수가 압도적으로 크지 않다면 우선순위 큐를 사용하여 푸는 편이 제일 편하다.

정렬할 대상을 담을 class를 선언할 때 Comarable을 implements해서 compareTo를 주어진 정렬조건에 맞게 우선순위대로 정렬하도록 오버라이딩 해주면 되기 때문이다.

비교대상이 정수일 경우 두 값의 차이를 반환하면되고,

아닌 것들(double, string 등..)은 해당 래퍼 클래스에 구현된 compareTo()로 비교 결과를 반환하면 된다.

정렬을 오름차순, 내림차순으로 하는지에 따라 비교 순서를 신경써야 함에 유의하자.

import java.util.*;

class Solution {
    static class File implements Comparable<File>{
        int idx, number;
        String name;
        File(int idx, String name, int number){
            this.idx = idx;
            this.name = name;
            this.number = number;
        }
        @Override
        public int compareTo(File o){
            if(this.name.compareTo(o.name)==0) {
                if(this.number==o.number) return this.idx - o.idx;
                else return this.number - o.number;
            }else return this.name.compareTo(o.name);
        }
    }

    public String[] solution(String[] files) {
        PriorityQueue<File> queue = new PriorityQueue<File>();
        int len = files.length;

        for(int i=0; i<len; i++){
            int j=-1, k=-1, file_len=files[i].length();
            for(j=0; j<file_len; j++){ // Number 시작구간 탐색
                char c = files[i].charAt(j);
                if(c>='0' && c<='9') {
                    k = j;
                    while(++k<file_len){ // Number 끝구간 탐색
                        char end = files[i].charAt(k);
                        if(end<'0' || end>'9') break;
                    }
                    break;
                }
            }

            String name = files[i].substring(0,j).toLowerCase();
            int number = Integer.parseInt(files[i].substring(j, k));
            queue.add(new File(i, name, number));
        }

        String[] answer = new String[len];
        for(int i=0; i<len; i++){
            answer[i] = files[queue.poll().idx];
        }

        return answer;
    }
}