[백준 1181] 단어 정렬

 

 

Comparator 구현해서 5분만에 풀었다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        String a[] = new String[n];
        
        for(int i=0; i<n; i++)
            a[i] = sc.next();
        
        Arrays.sort(a, new Comparator<String>() {
            public int compare(String s1, String s2) {
                if(s1.length() == s2.length()) {
                    for(int i=0; i<s1.length(); i++) {
                        if(s1.charAt(i) == s2.charAt(i))
                            continue;
                        else
                            return s1.charAt(i) - s2.charAt(i);
                    }
                }
                return s1.length() - s2.length();
            }
        });
        
        String prevStr = "";
        for(int i=0; i<a.length; i++) {
            if(prevStr.equals(a[i]))
                continue;
            System.out.println(a[i]);
            prevStr = a[i];
        }
    }
}

 

 

 

풀고 보니 정렬 방법을 직접 구현하는것이 문제의 의도가 아닐까 싶어서 다시 풀었다.

 

퀵정렬은 최악일 경우 O(n^2) 의 시간이 걸릴 수 있는데 피벗 선택을 여러가지로 해봐도 계속

시간 초과가 났다.

 

배열의 left, mid, right 중 중간값을 피벗으로 선택해서 풀면 뭔가 될 것 같으니 나중에 다시 해보기로 하고

일단은 합병정렬로 풀었다.

 

 

 

public class Main {
    
    static String temp[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        String a[] = new String[n];
        temp = new String[n];
        
        for(int i=0; i<n; i++)
            a[i] = br.readLine();
        
        divide(a, 0, n-1);
        String prevStr = "";
        for(int i=0; i<a.length; i++) {
            if(prevStr.equals(a[i]))
                continue;
            bw.write(a[i] + "\n");
            prevStr = a[i];
        }
        bw.flush();
        bw.close();
    }
    
    public static int cmp(char c1[], char c2[]) {
        if(c1.length == c2.length) {
            for(int i=0; i<c1.length; i++) {
                if(c1[i] != c2[i]) return c2[i] - c1[i];
            }
            return 0;
        } else return c2.length - c1.length;
    }
    
    public static void divide(String a[], int left, int right) {
        int mid = (left + right)/2;
        if(left < right) {
            divide(a, left ,mid);
            divide(a, mid+1, right);
            merge(a, left, mid, right);
        }
    }
    
    public static void merge(String a[], int left, int mid, int right) {
        int leftFirst = left;
        int rightFirst = mid+1;
        
        int leftIndex = left;
        while(leftFirst <= mid && rightFirst <= right) {
            if(cmp(a[leftFirst].toCharArray(), a[rightFirst].toCharArray()) > 0)
                temp[leftIndex++] = a[leftFirst++];
            else
                temp[leftIndex++] = a[rightFirst++];
        }
        
        if(leftFirst > mid) {
            for(int i=rightFirst; i<=right; i++)
                temp[leftIndex++] = a[i];
        } else {
            for(int i=leftFirst; i<=mid; i++)
                temp[leftIndex++] = a[i];
        }
        for(int i=left; i<=right; i++)
            a[i] = temp[i];
    }
    
}

 

 

메모리는 3배썼지만 속도가 2.5배 빨라졌다.