백준 1181번 (단어 정렬) c++

문제

문제풀이

이 문제는 구조체, 정렬과 문자열에 대해 잘 알고 있다면 쉽게 풀 수 있다.

 

struct Input{
        char word[51];
        int len;
};

먼저 단어와 단어의 길이를 저장하는 구조체를 선언해준다.

 

        for(register int i = 0; i < N; i++){

                char in_temp[51] = {0,};

                cin >> in_temp;

                int exist = 0;

                for(register int j = 0; j < input_cnt; j++){
                        if(!strcmp(input[j].word, in_temp)){
                                exist = 1;
                                break;
                        }
                }

                if(!exist){

                        strcpy(input[input_cnt].word, in_temp);

                        int temp = 0;

                        while(input[input_cnt].word[temp]){
                                temp++;
                        }

                        input[input_cnt++].len = temp;
                }

        }

그리고 단어를 입력받는다.

여기서, 중요한 점이 있다. 

바로 중복된 단어는 하나만 출력해야한다는 조건이다.

그래서 나는 단어들을 받을 때마다 기존 구조체에 존재하는지 확인하고, 존재한다면 입력받지 않았다.

 

// strcmp 문자열을 비교하는 함수

// strcpy 문자열을 복사하는 함수

 

존재 하지 않는다면 입력받고 길이를 같이 구하여 저장해주었다.

 

이제 가장 핵심인 부분이다.

입력 받은 단어들을 어떻게 조건에 맞게 정렬할 것인가?

 

int comp(const Input& a, const Input& b){

        if(a.len == b.len){

                int temp = 0;

                for(register int i = 0; i < a.len; i++){
                        if(a.word[i] != b.word[i]){
                                temp = i;
                                break;
                        }
                }

                return a.word[temp] < b.word[temp];

        }

        else return a.len < b.len;

}


sort(input, input + input_cnt, comp);

구조체 정렬을 할때는 이렇게 비교하는 함수를 만들어 내가 필요한 조건들을 만들어 정렬을 시킬 수 있다.

 

sort(시작주소, 끝주소, 비교함수)

이렇게 sort 함수를 쓴다.

 

각각의 길이를 비교하고, 만약 길이가 같다면 각각의 단어들을 하나씩 비교하면 된다.

 

 

전체코드

#include <bits/stdc++.h>

using namespace std;

struct Input{

        char word[51];
        int len;

};

Input input[20001];
int input_cnt;

int comp(const Input& a, const Input& b){

        if(a.len == b.len){

                int temp = 0;

                for(register int i = 0; i < a.len; i++){
                        if(a.word[i] != b.word[i]){
                                temp = i;
                                break;
                        }
                }

                return a.word[temp] < b.word[temp];

        }

        else return a.len < b.len;

}

int main(){

        ios_base::sync_with_stdio(false);
        cin.tie(0);

        int N;

        cin >> N;

        for(register int i = 0; i < N; i++){

                char in_temp[51] = {0,};

                cin >> in_temp;

                int exist = 0;

                for(register int j = 0; j < input_cnt; j++){
                        if(!strcmp(input[j].word, in_temp)){
                                exist = 1;
                                break;
                        }
                }

                if(!exist){

                        strcpy(input[input_cnt].word, in_temp);

                        int temp = 0;

                        while(input[input_cnt].word[temp]){
                                temp++;
                        }

                        input[input_cnt++].len = temp;
                }

        }

        sort(input, input + input_cnt, comp);

        for(register int i = 0; i < input_cnt; i++){
                cout << input[i].word << '\n';
        }

        return 0;

}