[24/11/27] 정렬 퀵소트

5648

 

어려운문제는 아니다. 그냥 뒤집고 정렬하고 출력하면 된다.

Arrays.sort(배열)의 시간이 최악의 상황에서도 O(nlogn)이라 그냥 애매하면 내장함수가 젤 빠르니까 이걸 쓰면 되긴 한다.

하지만 퀵소트를 공부하는 입장에서 구현해보고 있기에 내장함수로 한번 , 퀵소트로 한번 구현해봤다.

 

시간은 10^6의 입력값 n에다가 정수가 10^12를 벗어나면 안되니까 내 코드에서는 12자리, 즉 하나의 숫자당 최대 12번을 탐색하면서 숫자를 거꾸로 뒤집는다.

 

정렬할때 브루트포스의 O(n^2)의 짓거리만 안하면 다 통과된다.

 

 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n= Integer.parseInt(st.nextToken());
        long[] arr = new long[n];
        long[] newArr = new long[n];
        int count =0;
        while(count<n){
            while(st.hasMoreTokens()){
                String temp ="";
                String k = st.nextToken();
                for(int i=k.length()-1; i>=0; i--){
                    temp+=k.charAt(i);
                }
                newArr[count++]=Long.parseLong(temp);
            }
            if(count>=n){
                break;
            }
            st=new StringTokenizer(br.readLine());
        }
        quickSort(newArr,0,newArr.length-1);
        for(int i=0; i<newArr.length; i++){
            System.out.printf("%d\n",newArr[i]);
        }
        

        
    }
    public static void quickSort(long[] arr, int start ,int end){
        if(start>=end){
            return;
        }
        int pivot= (end+start)/2;
        swap(arr,start,pivot);
        pivot=start;
        int startIndex=start+1;
        int endIndex=end;
        while(startIndex<=endIndex){
            while(startIndex<=end && arr[startIndex]<=arr[pivot]){
                startIndex++;
            }
            while(endIndex>=start+1 && arr[endIndex]>=arr[pivot]){
                endIndex--;
            }
            if(startIndex<=endIndex){
                swap(arr,startIndex++,endIndex--);
            }
        }
        swap(arr,endIndex,pivot);
        pivot=endIndex;
        quickSort(arr,start,pivot-1);
        quickSort(arr,pivot+1,end);
    }
    
    public static void swap(long[] arr, int a, int b){
        long temp = arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
}

이것은 퀵소트로 푼 풀이.

 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n= Integer.parseInt(st.nextToken());
        long[] arr = new long[n];
        long[] newArr = new long[n];
        int count =0;
        while(count<n){
            while(st.hasMoreTokens()){
                String temp ="";
                String k = st.nextToken();
                for(int i=k.length()-1; i>=0; i--){
                    temp+=k.charAt(i);
                }
                newArr[count++]=Long.parseLong(temp);
            }
            if(count>=n){
                break;
            }
            st=new StringTokenizer(br.readLine());
        }
        Arrays.sort(newArr);
        for(int i=0; i<n; i++){
            System.out.printf("%d\n",newArr[i]);
        }

        
    }
}

내장함수 풀이