[백준 1181] 단어정렬 (vector, array)

• 안녕하세요!! BlockDMask 입니다.

• 오늘의 문제 포스팅 하겠습니다.

0. 제목

• 백준 1181 단어정렬

• BOJ 1181 단어정렬

1. 문제 설명

N개의 단어가 들어오면 
1) 길이가 짧은순

2) 길이가 같으면 사전순

으로 정렬하여 출력하는 문제입니다.

(단어는 소문자만 들어옵니다)

(중복 제거 해야합니다.)

2. 풀이 과정

처음에는 vector container를 이용하여서,

sort 알고리즘을 이용하여 정렬을하고

unique 알고리즘을 이용하여 중복을 제거한 후 

iterator(반복자)를 이용하여 출력하는것으로 문제를 풀었습니다.

그런데 다른사람과 비교했을때, 걸린 시간과 메모리량이 큰 것을 보고.

어떻게 줄인걸까 생각을 해봤습니다.

그래서.

총 4가지 방법으로 문제를 풀어봤습니다.

T1) 방식이 제가 처음에 문제를 푼 방식이었습니다.

T1) vector, iterator 이용 / C++ 스타일의 (cout, cin) 입출력 사용.

T2) vector, iterator 이용 / C 스타일의 (printf, scanf) 입출력 사용.

T3) 구조체, array 이용 / C++ 스타일의 (cout, cin) 입출력 사용.

T4) 구조체, array 이용 / C 스타일의 (printf, scanf) 입출력 사용.

3. 코드

T1) vector, iterator 이용 / C++ 스타일의 (cout, cin) 입출력 사용.

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
//sort 의 기준이 되는 함수. 
bool comp(const string &s1,const string &s2){
    
    if(s1.size() == s2.size()){ //사이즈가 같으면, 사전순 앞으로. 
        return s1 < s2;
    }
    return s1.size() < s2.size();    //사이즈 다르면 작은게 앞으로. 
    
}
 
int main(void){
    vector<string> v;
    
    int n;
    cin >> n;
    
    string str;
    
    for(int i=0; i<n; i++){
        cin >> str;
        v.push_back(str);    
    }    
    
    vector<string>::iterator iter; 
    vector<string>::iterator end_iter; 
 
    sort(v.begin(), v.end(), comp);    //정렬.
 
    end_iter = unique(v.begin(), v.end());     //중복 제거
    //중복이 제거 된 후 size는 동일하기 때문에,
    //중복 의 마지막 end_iter를 받습니다. 
 
    for(iter = v.begin(); iter !=end_iter ; iter++){
        cout << *iter << endl;    
    }
    
    return 0;    
}

T2) vector, iterator 이용 / C 스타일의 (printf, scanf) 입출력 사용.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
 
//sort 의 기준이 되는 함수. 
bool comp(const string &s1,const string &s2){
    
    if(s1.size() == s2.size()){ //사이즈가 같으면, 사전순 앞으로. 
        return s1 < s2;
    }
    return s1.size() < s2.size();    //사이즈 다르면 작은게 앞으로. 
    
}
 
int main(void){
    vector<string> v;
    
    int n;
    scanf("%d", &n); //C style
    
    for(int i=0; i<n; i++){
        char c[51];
        scanf("%s", c); //C style
        string str(c);
        v.push_back(str);    
    }    
    
    vector<string>::iterator iter; 
    vector<string>::iterator end_iter; 
    
    sort(v.begin(), v.end(), comp);    //정렬.
    
    end_iter = unique(v.begin(), v.end());     //중복 제거
    //중복이 제거 된 후 size는 동일하기 때문에,
    //중복 의 마지막 end_iter를 받습니다. 
    
    for(iter = v.begin(); iter !=end_iter ; iter++){
        printf("%s\n", (*iter).c_str()); //C++ style string을 C style로 출력.
    }
    
    return 0;    
}

T3) 구조체, array 이용 / C++ 스타일의 (cout, cin) 입출력 사용.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
 
//구조체, C++ style. 
struct Word{
    int len;
    char arr[51];
};
 
//sort 의 기준이 되는 함수. 
bool comp(const Word &s1,const Word &s2){
    
    if(s1.len == s2.len){ //사이즈가 같으면, 사전순 앞으로. 
        for(int i=0; i< s1.len; i++){
            if(s1.arr[i] == s2.arr[i]) continue;
            else if(s1.arr[i] < s2.arr[i]) return true;
            else return false;
        }
    }
    return s1.len < s2.len;    //사이즈 다르면 작은게 앞으로. 
    
}
 
int main(void){
    int n;
    cin >> n;    //C++ style
    
    Word *word = new Word[n]; //동적할당 
    
    for(int i=0; i<n; i++){
        cin >> word[i].arr;    //C++ style
        word[i].len = strlen(word[i].arr);
        
    }    
    
    sort(word, word+n , comp);    //정렬.
    
    for(int i=0; i<n; i++){    //배열을 이용한 출력. 
        if(i!=0){
            if(!strcmp(word[i].arr, word[i-1].arr)){ //
                continue;
            }
        }
        cout << word[i].arr << endl;     //C++ style
    }
    
    delete []word; //동적할당 해제 
    return 0;
}

T4) 구조체, array 이용 / C 스타일의 (printf, scanf) 입출력 사용.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
 
//구조체, C++ style. 
struct Word{
    int len;
    char arr[51];
};
 
//sort 의 기준이 되는 함수. 
bool comp(const Word &s1,const Word &s2){
    
    if(s1.len == s2.len){ //사이즈가 같으면, 사전순 앞으로. 
        for(int i=0; i< s1.len; i++){
            if(s1.arr[i] == s2.arr[i]) continue;
            else if(s1.arr[i] < s2.arr[i]) return true;
            else return false;
        }
    }
    return s1.len < s2.len;    //사이즈 다르면 작은게 앞으로. 
    
}
 
int main(void){
    int n;
    scanf("%d", &n); //C style
    
    Word *word = new Word[n]; //동적할당. 
    
    for(int i=0; i<n; i++){
        scanf("%s", word[i].arr); //C style
        word[i].len = strlen(word[i].arr);
        
    }    
    
    sort(word, word+n , comp);    //정렬.
    
    for(int i=0; i<n; i++){ //배열을 이용한 비교. 
        if(i!=0){
            if(!strcmp(word[i].arr, word[i-1].arr)){ //중복제거 
                continue;
            }
        }
        printf("%s\n", word[i].arr); //C style
    }
    
    delete []word; //메모리 할당 해제 
    return 0;
}

4. 인증 및 결과 비교.

T1) vector, iterator 이용 / C++ 스타일의 (cout, cin) 입출력 사용.

T2) vector, iterator 이용 / C 스타일의 (printf, scanf) 입출력 사용.

T3) 구조체, array 이용 / C++ 스타일의 (cout, cin) 입출력 사용.

T4) 구조체, array 이용 / C 스타일의 (printf, scanf) 입출력 사용.

5. 결론

메모리와 시간을 비교해보겠습니다.

cout, cin < prinf, scanf 가 속도면에서 빠르다.

이번 문제의 경우에는 vector를 이용하여 푸는 것 보다

배열을 이용하여 푸는게 메모리가 적게 들었다.

cout, cin 보다 printf, scanf 가 속도면에서 빠르다는 것은 알고 있었지만

숫자로 직접 확인해보니 차이가 많이 나는 것을 몸소 느꼈습니다.

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

감사합니다.