[백준 1181] 단어 정렬

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

1/7일 문제

요구사항

1. 길이 오름차순

2. 길이 같으면 사전순으로

 

풀이

1. 퀵정렬은 최악이 n^2이라 머지로 정렬하였다.

 

#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;
 
const int PN = 23;
const int HASH_SIZE = 10000;


struct go{
    int size;
    char ch[51];
};
go map[20001];
go buf[20001];
int n;
/*
void qasort(int arr[], int left, int right){
    if(left>=right){
        return;
    }
    int i = left;
    int j = right;
    int pivot = arr[(left+right)/2];

    while(i<=j){
        while(arr[i]<pivot){
            i++;
        }
        while(arr[j]>pivot){
            j--;
        }
        if(i<=j){
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
            i++;
            j--;
        }
    }
    qasort(arr,left,j);
    qasort(arr,i,right);
}
*/
/*
void merge_sort(int arr[], int len){
    
    if(len<2)
        return;
    int i,j,mid,k;
    mid = len/2;
    i=0;
    k=0;
    j=mid;

    merge_sort(arr,mid);
    merge_sort((arr+mid),(len-mid));

    while(i<mid && j<len){
        if(arr[i]<arr[j]){
            buf[k++]=arr[i++];
        }
        else{
            buf[k++]=arr[j++];
        }
    }

    while(i<mid){
        buf[k++]=arr[i++];
    }

    while(j<mid){
        buf[k++]=arr[j++];
    }

    for(int i =0 ; i <len ; i++){
        arr[i]=buf[i];
    }
}
*/
void qasort(go arr[], int left, int right){
    if(left>=right)
        return;
    int i = left;
    int j = right;
    go pivot= arr[(left+right)/2];

    while(i<=j){
        while(arr[i].size < pivot.size){
            i++;
        }
        
        while(arr[j].size > pivot.size){
            j--;
        }
        if(arr[i].size == arr[j].size){
            for(int k=0 ; k<arr[i].size ; k++){
                if(arr[i].ch[j] > arr[j].ch[j]){

                }
                else{

                }
            }
        }
        if(i<=j){
            go temp;
            temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
            i++;
            j--;
        }
    }
    qasort(arr,left,j);
    qasort(arr,i,right);
}
void merge_sort(go arr[], int len){
    if(len<2){
        return;
    }
    int i,j,mid,k;
    mid=len/2;
    i=0;
    j=mid;
    k=0;
    merge_sort(arr,mid);
    merge_sort((arr+mid),(len-mid));

    while(i<mid && j <len){
        
        if(arr[i].size < arr[j].size){
            buf[k++]=arr[i++];
        }
        
        else if(arr[i].size == arr[j].size){
          //  cout<<arr[i].size<<endl;
            int flag=0;
            for(int len=0 ; len<arr[i].size ; len++){
         //       cout<<arr[i].ch[len]<<" "<<arr[j].ch[len]<<endl;
                if(arr[i].ch[len] < arr[j].ch[len]){
                    buf[k++]=arr[i++];
                    flag=1;
                    break;;
                }
                else if(arr[i].ch[len] > arr[j].ch[len]){
                    buf[k++]=arr[j++];
                    flag=1;
                    break;;
                }
            }
            if(flag==1)
                continue;
            else{
                buf[k++]=arr[i++];}

        }
        else{
            buf[k++]=arr[j++];
        }
    }

    while(i<mid){
        buf[k++]=arr[i++];
    }

    while(j<len){
        buf[k++]=arr[j++];
    }

    for(int k=0 ; k <len ; k++){
        arr[k]=buf[k];
    }

}
int strcmp(char a[], char b[])
{
    int i=0;
    int j=0;
    while(a[i]){
        if(a[i++] != b[j++]){
            i--,j--;
            break;
        }
    }
    return a[i]-b[j];
}
int main(){
    scanf("%d",&n);
    for(int i=0 ; i < n ; i++)
    {
        char ch[51];
        scanf(" %s",&map[i].ch);
        int cnt=0;
        for(int j=0 ; map[i].ch[j]!=0 ; j++){
            cnt++;
        }
        map[i].size=cnt;
    }
    //cout<<endl;
    merge_sort(map,n);
    // qasort(map,0,n-1);
  //  cout<<"A"<<endl;

    for(int i=0 ; i < n ; i++)
    {
     //   cout<<"A "<<map[i].ch<<endl;
        if(i!=n-1)
        {
            if(strcmp(map[i].ch, map[i+1].ch)==0)
            {
                continue;
            }
            else{
                printf("%s\n",map[i].ch);
            }
        }
        else{
            printf("%s\n",map[i].ch);
        }

    }
}