백준 1181번, 단어 정렬

백준 1181번 c++ 문제풀이

문제: 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다.
   

풀이:

정렬 알고리즘을 이용해서 풀어야 한다. quick sort를 구현해서 단어 정렬 후 출력하는 식으로 접근했다.

#include <iostream>

using namespace std;

void quicksort(int start, int end, string *in){

if(start >= end){
    return ;
}

int pivot = start;
int i= pivot + 1;
int j = end;

while( i <= j){
    while(i <= end && in[i].length() <= in[pivot].length()){ //처음부터 시작해서 pivot값보다 작으면 i 증가(pivot값보다 크다면 중지)
    if(in[i].length() == in[pivot].length()){
        if(in[i] > in[pivot]){ //둘이 길이는 같은데 사전 순서가 i가 더빠르면 pivot보다 크다 생각헤 중지
        break;
        }
    }
    i++;
    }
    while(j > start && in[j].length() >= in[pivot].length()){//뒤부터 시작해서 pivot값보다 크면 j증가(pivot값보다 작다면 중지)
    if(in[j].length() == in[pivot].length()){
        if(in[j] < in[pivot]){//둘이 길이는 같은데 사전 순서가 j가 더느리면 pivot보다 작다 생각헤 중지
            break;
        }
    }
    j--;
    }

    if(i > j){ //만약 위의 반복문을 통해 i가 j보다 크다면 pivot값과 j값을 교체
    in[j].swap(in[pivot]);
    }else{//아니면 i랑 j의 위치를 바꾼다.
    in[j].swap(in[i]);
    }
}

    quicksort(start, j-1, in);
    quicksort(j+1,end,in);
}

int main(){
    int num;
    string input[20000];
    cin >> num;

    for(int i=0;i<num;i++){
        cin >> input[i];
    }

    

    quicksort(0,num-1,input);


    for(int i=0;i<num;i++){
        if(input[i] ==input[i-1]){
        continue;
        }
        cout << input[i] <<"\n";
    }
    return 0;
}

위의 코드를 작성 후 돌려보니 시간 초과가 나왔다..
내가 작성한 quick sort가 이상한건지.. 아니면 다른 이유가 있는건지 아시는 분은 알려주시기 바랍니다..

그래서 다시 코드를 다시 짜기로 하고 c++에서 제공하는 sort 알고리즘을 사용해서 풀었다.
sort 알고리즘은 quick sort기반으로 함수가 구현되어 있다.
그래서 따로 quick sort를 구현하지 않아도 된다는 장점이 있다.

최종 코드:

#include <iostream>
#include <algorithm>

using namespace std;

bool compare(string a, string b){
if(a.length() == b.length()){
    return a < b;   //길이가 같다면 사전순 
}
else{
    return a.length() < b.length();//아니면 길이순
}
}

string input[20000];

int main(){
    int num;
    cin >> num;

    
    for(int i=0;i<num;i++){
        cin >> input[i];
    }//벡터에 단어 저장

    sort(input, input + num, compare);



    for(int i=0;i<num;i++){
        if(input[i] ==input[i-1]){
        continue;
        }
        cout << input[i] <<"\n";

    }
    return 0;
}

위 코드는 통과 했습니다.
compare 함수를 이용하여 sort함수의 기준을 세워주었다.
sort의 세번째 인자에 사용자 정의 함수를 넣으면 그 기준으로 정렬 가능합니다.

return 0; 이전의 for문을 통해 이전과 중복이 된다면(이미 순서대로 정렬 되었기에 앞뒤만 확인하면 된다.) 출력되지 않게 해서 중복 출력을 제거 했습니다.

감사합니다.