프로그래머스 Lv.2) 파일명 정렬

2018 KAKAO BLIND RECRUITMENT [3차]

파일명 정렬

코딩테스트 연습 - [3차] 파일명 정렬

풀이

문제를 푸는데 시간이 꽤 걸렸다. 처음에는 head, number, tail 그리고 파일명을 담는 클래스를 만들어, 우선순위큐에 조건에 따라 저장될 수 있게 설정해주었는데, 모든 조건이 같은경우 먼저 들어온 파일이 우선순위가 된다는 조건을 설정할 때, 매우 불안정했다. 그래서 테스트케이스에서 4문제인가 밖에 통과하지 못했다. 그래서 잠깐의 휴식을 취한 뒤에, 직접 조건에 따라 배열에 저장해주기로 했다.

 

또한, 문제를 다시 읽어보니 tail이 필요 없어서 파일 이름, head, number를 담는 FileInfo 클래스를 만들었다. 문자열을 돌면서 head와 number를 구해주었고, head에 담기는 문자는 대소문자 구분이 필요 없다는 조건때문에, 모든 소문자를 대문자로 변경한 뒤 저장해주었다.

 

이후에 FileInfo 클래스를 조건에 맞게 저장할 SortedFiles 클래스를 만들었다. isFast라는 메소드를 만들어 로직을 검사했는데, 모든 조건에 따라 if문을 걸어주었다. 기존의 file과 새로 들어온 file 중 더 짧은 Head에 따라서 사전 순서를 검사해주면서 기존 파일이 더 빠른 조건이면 true를, 새로 들어올 파일이 더 빠른 조건이면 false를 리턴해주었다. Head 검증이 끝난 뒤에는, 둘 중 잔여 문자가 남아있는지 확인하고, 더 긴 Head에 따라 리턴해줬다. 이후에는 number 검증을 통해 더 빠른 파일을 정했고, number까지 같다면 기존 파일이 더 앞에 저장되도록 설정했다.

 

모든 파일의 저장이 끝난 뒤에는 파일 이름을 담을 배열에 순서대로 저장해주면서 리턴해주었다.

 

문제를 풀면서 꼬였던 부분은

1. isFast 메소드에서 head 검증 후, 남은 문자열 길이를 확인하는 부분

2. head와 number를 자를 때, number가 제대로 잘리지 않은 부분

두 가지 정도였다.

 

간략하게 다시 로직을 설명하면,

1. file의 이름과 head, number를 저장할 클래스를 만들고, 문제의 조건에 따라 저장한다.

2. file의 순서를 담을 class를 만들어, 문제 조건에 따라 순서를 정해준다.

 2-1. head를 검증할 때, out of idx 방지를 위해 더 짧은 head 길이만큼 돌것.

 2-2. head검증 후에, 검증하지 못한 문자가 남아있는지 확인해서 return 조건을 달아줄 것.

 2-3. number를 검증해서 return 해준다.

 2-4. 위의 세 절차에서 결론이 나지 않았다면, 기존 파일을 더 앞에 둘 것

 

코드

class Solution {
    public String[] solution(String[] files) {
        SortedFiles sf = new SortedFiles(files.length);
        
        for(String file : files) {
            sf.addFile(file);
        }
        return sf.getResult();
    }
}

class SortedFiles {
    private String[] result;
    private FileInfo[] fileArr;
    int top;
        
    public SortedFiles(int n) {
        result = new String[n];
        fileArr = new FileInfo[n];
        top = -1;
    }
    
    public void addFile(String name) {
        FileInfo file = new FileInfo(name);
        // System.out.println(file.name + "\t" + file.head +  file.number);
        if(top == -1) {
            fileArr[++top] = file;
        } else {
            for(int i=top; i>=0; i--) {
                if(isFast(fileArr[i], file)) {  // origin이 더 빠르면
                    fileArr[i+1] = file;
                    break;
                } else {    // target이 더 빠르면
                    fileArr[i+1] =  fileArr[i];
                    fileArr[i] = file;
                }
            }
            top++;
        }
    }
    
    private boolean isFast(FileInfo origin, FileInfo target) {
        int len = Math.min(origin.head.length(), target.head.length());
        for(int i=0; i<len; i++) {
            char originCh = origin.head.charAt(i);
            char targetCh = target.head.charAt(i);
            if(originCh < targetCh) {   // origin이 더 빠름
                return true;
            } else if(originCh > targetCh) {    // target이 더 빠름
                return false;
            }
        }
        if(origin.head.length() != len) {    // target이 더 빠름
            return false;
        } else if(target.head.length() != len) { // origin이 더 빠름
            return true;
        }
        if(origin.number < target.number) { // origin이 더 빠름
            return true;
        } else if(origin.number > target.number) {  // target이 더 빠름
            return false;
        }
        
        return true;    // 모두 같은경우 origin이 더 빨라야함
    }
    
    public String[] getResult() {
        for(int i=0; i<this.result.length; i++) {
            result[i] = this.fileArr[i].name;
            // System.out.println(this.fileArr[i].name + "\t" + this.fileArr[i].head + "\t" + this.fileArr[i].number);
        }
        return this.result;
    }
}

class FileInfo {
    String name;
    String head;
    int number;
    
    public FileInfo(String file) {
        name = file;
        int lastIdx =0;
        for(int i=0; i<file.length(); i++) {
            char ch = file.charAt(i);
            if(ch >=48 && ch <=57) {
                break;
            }
            lastIdx=i;
        }
        this.head = getStandard(file.substring(0,lastIdx+1));
        
        for(int i=lastIdx+1; i<file.length(); i++) {
            char ch = file.charAt(i);
            if(ch >57 || ch <48) {// 숫자가 아닌 경우
                break;
            }
            lastIdx = i;
        }
        
        this.number = Integer.parseInt(file.substring(this.head.length(), lastIdx+1));
    }
    
    private String getStandard(String str) {
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<str.length(); i++) {
            char ch = str.charAt(i);
            if(ch >=97 && ch <=122) {
                ch-=32;
            }
            sb.append(ch);
        }
        return sb.toString();
    }
}