백준 1181번 - 단어 정렬 문제 C++

📍 백준 1181번 - 단어 정렬 문제 C++

🧩 문제 요약 

N개의 문자가 입력된다. 

길이가 짧은 순 부터 사전순으로 나열한다. 

 

이 문제는 간단하지만 처음에 string을 어떻게 정렬할 수 있을지 몰라서 실마리를 찾기가 어려웠다.

그래서 결국 서칭을 통해 답을 얻었다. 

 

👍 이 코드에서 배울 점 

#include <iostream>
#include <string> 
#include <algorithm>

using namespace std; 

bool CompStr(string a, string b){
    if(a.length() != b.length()){
        return a.length()<b.length(); // 길이 비교
    }else{
        return a<b; //사전순 나열
    }
}

int main(){
    ios::sync_with_stdio(false);

    int N, i ; 
    cin >> N ;
    string str[20000];
    for(i = 0; i<N; i++){
        cin >> str[i];
    }
    
    sort(str, str+N, CompStr);
    for(i = 0; i<N; i++){
        if(str[i]==str[i-1]) continue ;  // 중복제거 
        else cout << str[i] << "\n";
    }

}

 

 

✅ 입력 방법

지금까지 계속 scanf와 printf를 고집했던 것은 속도가 빠르고 백준의 상위권 코드들이 모두 scanf와 printf를 사용하기 때문이였다. 하지만 확인해본 결과 cin, cout을 사용하더라도 아래와 같이 stdio와의 sync를 끊어 주고 입력 출력이 묶여 있는 것을 끊어 주면 비슷한 속도를 가진 다는 것을 알게 되었다. 

ios::sync_with_stdio(false);
cin.tie(NULL);

 

여러가지 변수 타입에 구애 받지 않고, 무엇보다 string을 입력받는 것에서 cin, cout이 매우 매우 편리하기 때문에 앞으로는 iostream을 사용하고 위의 선언으로 속도를 챙기려고 한다. 

 

✅ sort함수 

sort함수는 algorithm헤더에 포함되어 있다. 

sort()함수는 기본적으로 오름차순 정렬을 수행한다. 

배열의 시작점 주소와 마지막 주소 +1을 인자로 받는다. 

#include <algorithm>

int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
sort(arr, arr+10);

 

 

👉 C++의 sort() 함수는 정렬의 기준을 정할 수 있다.

때문에, 많이들 Compare()라는 함수를 만들어서 자신만의 기준으로 정렬을 하는 식으로 변경해서 사용한다. 

sort()의 세번째 인자 값으로 정의한 비교함수를 넣게 되면 해당 함수의 반환 값에 맞게 정렬이 동작한다. 

bool CompStr(string a, string b){
    if(a.length() != b.length()){
        return a.length()<b.length(); // 길이 비교
    }else{
        return a<b; //사전순 나열
    }
}

sort(str, str+N, CompStr);

 

 

✅ 사전순 나열 

C++에서는 string 끼리 "<"를 비교하면 자동으로 사전순 비교를 해준다. 

이는 C++표준 라이브러리의 std::string은 내부적으로 operator< 연산자가 오버로딩 되어 있어서, 문자열을 사전식( (lexicographical) 으로 비교하게 되어 있다. 

그래서 우리는 아주 간단하게 사전식 순서를 비교할 수 있다. 

 

 

이 문제는 단순해 보이지만 많은 것들을 배울 수 있었다. 

백준의 상위 코드들은 아래와 같이 더 빠르고 효율적인 방법을 찾아서 코드를 작성했는데, 

이런 멋쟁이 레벨이 되기 위해서 아직은 한참 지식이 필요하다. ㅠ 

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

char wbuf[1<<20];
char rbuf[1<<20];
int ridx, nidx, widx;

inline char read(){
    if(ridx == nidx){
        nidx = fread(rbuf, 1, 1<<20, stdin);
        if(!nidx) return 0;
        ridx = 0;
    }
    return rbuf[ridx++];
}

inline int readInt(){
    int sum = 0;
    char now = read();
    
    while(now <= 32) now = read();
    while(now >= 48) sum = sum * 10 + now - '0', now = read();
    
    return sum;
}

inline void readChar(char c[51]){
    char now = read();
    char tmp[51];
    int idx = 0;
    while(now <= 32) now = read();
    while(now >= 48) tmp[idx++] = now, now = read();
    
    tmp[idx] = '\0';
    strcpy(c, tmp);
}

inline void bflush(){
    fwrite(wbuf, 1, widx, stdout);
    widx = 0;
}

inline void write(char c){
    if(widx == (1<<20)) bflush();
    wbuf[widx++] = c;
}

inline void writeChar(char c[51]){
    int isz = 1;
    while(c[isz] != '\0') isz++;
    if(isz + widx >= (1<<20)) bflush();
    
    for(int i = 0; i<isz; i++){
        wbuf[widx++] = c[i];
    }
    write('\n');
}

struct Word {
    int length;
    char word[51];
};

bool compare(const Word& a, const Word& b) {
    if(a.length == b.length){
        if(strcmp(a.word, b.word) <0) return true;
        else return false;
    }
    return a.length < b.length;
}

Word w[20001];

int main(void) {
    int N = readInt();
    char tmp[51];
    for (int i = 0; i < N; i++) {
        readChar(w[i].word);
        w[i].length = strlen(w[i].word);
    }
    std::sort(w, w + N, compare);
    writeChar(w[0].word);
    for (int i = 1; i < N; i++) {
        if (strcmp(w[i].word, w[i - 1].word)) writeChar(w[i].word);
    }
    bflush();
}