[1181번] 단어 정렬

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. sort의 정렬 수식 세우기

2. pair에 대한 생각

사실 이 문제는 pair를 빼고 그냥 풀어도 된다.(아래 코드를 보면 .second가 하나도 없다.)

아래 코드의 comp를 자세히 보면 1181번 문제의 조건에 대한 내용이 모두 들어있다.

1. 길이가 짧은 순서대로 :: if (a.first.length() < b.first.length())

2. 길이가 같다면 사전 순으로 :: 

else if (a.first.length() == b.first.length())

        return (strncmp(a.first.c_str(), b.first.c_str(), a.first.length()) < 0);

이 두가지 코드를 통해 모든 것을 해결 할 수 있게된다.

pair을 쓴 이유는 각 문자열의 합을 아스키 코드로 표현하면 어떨까하여 생각해 보았지만 치명적인 오류가 날 수 있기에 생략하였다.

즉, 아스키 코드의 총합이 같은 다른 문자열들은 정렬이 어떻게 될 지 확신할 수 없기 때문에 위험한 코드가 될 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <algorithm>   using namespace std;   pair<string, int> str[20001];   bool comp(const pair<string, int> &a, const pair<string, int> &b) {     if (a.first.length() < b.first.length())         return true;       else if (a.first.length() == b.first.length())         return (strncmp(a.first.c_str(), b.first.c_str(), a.first.length()) < 0);       return false; }   int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n; i++)     {         cin >> str[i].first;           for (int t = 0; t < str[i].first.size(); t++)             str[i].second += (int)str[i].first.at(t);     }       sort(str, str + n, comp);          cout << str[0].first << endl;     for (int i = 1; i < n; i++)     {         if (i > 0 && str[i].first == str[i - 1].first)             continue;           cout << str[i].first << endl;     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus