[백준 C++] 1599번 민식어

1599번: 민식어

문제 요약

문제

무엇인가를 창조하는 것은 어렵다. 오민식은 지금까지 어려운 다른나라의 언어를 쓰면서 백성들이 고통에 받는 것을 슬퍼하고 새로운 언어를 만들고자 했다. 그는 창조의 고통에 시달리던 중에 결국 오영식에게 자신의 못다 이룬 꿈을 꼭 이루어달라면서 오영식에게 창조의 임무를 넘겼다.

오영식은 자신의 형이 창조에 고통에 시달리는 모습을 보고 마음이 아파서 자신은 창조를 하지 않기로 했다. 영식이는 표절을 하기로 했는데 세계적인 추세에 맞게 영어를 표절하기로 했다.

영식이는 자신의 형의 이름을 따서 민식어라고 이름붙였다.

민식어에는 알파벳이 20개가 있다.

영어는 a b c d e f g h i j k l m n o p q r s t u v w x y z의 순서이지만, 민식어는 a b k d e g h i l m n ng o p r s t u w y의 순서이다.

민식어는 영어의 순서를 따르기는 하지만, 약간 변형시켜서 따른다. 그리고 ng는 n과 o사이에 오는 하나의 알파벳이다. ng는 무조건 이 알파벳으로 생각한다.

영식이는 사람들이 쉽게 민식어를 배울 수 있도록 민식어 사전을 만들려고 한다. 따라서 몇 개의 단어를 정렬하고자 한다. 민식어 단어가 주어졌을 때, 그것을 민식어의 순서대로 정렬하는 프로그램을 작성하시오.

사용 알고리즘

정렬, 구현

입출력

• 입력: 첫째 줄에 민식어 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 한 줄에 하나씩 단어가 입력으로 들어온다. 단어의 길이는 최대 50자이다. 민식어에 없는 알파벳이 입력으로 주어지는 경우는 없다. 모든 단어는 중복되지 않는다.
• 출력: 첫째 줄부터 차례대로 정렬한 결과를 출력한다. ``` 예제1

입력 6 ang ano anim alak alam alab 출력 alab alak alam anim ano ang

## 풀이
민식어의 특이한 점은 ng가 한글자로 본다는 점이다. 이를 좀더 편하게 하기 위해 ng를 다른 알파벳(c)로 바꿔주는 함수와 그것을 다시 원래 ng로 바꿔주는 함수를 만들었다. 이를 통해 정렬할때 ng라는 두글자가 아닌 한글자로 보고 풀 수 있게 되었다. 나머지는 어렵지 않다. c++에서 제공하는 sort함수는 3번째 인자로 비교함수를 받는다. 따라서 민식어 전용 비교 함수를 만들어서 해결하면 된다. 민식어의 알파벳을 사전순으로 정렬한 배열을 만들고 각 글자가 몇번째에 있는지 비교하면 된다.

## 어려웠던 점


## 배운 점 / 느낀 점


## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
char dict[] = {'a', 'b', 'k', 'd', 'e', 'g', 'h', 'i', 'l', 'm', 'n', 'c', 'o', 'p', 'r', 's', 't', 'u', 'w', 'y'};
vector<string> l;

bool comp(string a, string b){
    for(int i = 0; i < a.size() && i < b.size(); i++){
        char a_target = a[i];
        char b_target = b[i];
        auto ait = find(begin(dict), end(dict), a_target);
        auto bit = find(begin(dict), end(dict), b_target);
        if(ait != bit){
            return ait < bit;
        }
    }
    return b.size() > a.size();
}

string ng2c(string a){
    string b = "";
    for(int i = 0; i < a.size(); i++){
        if(a[i] == 'n'){
            if(a[++i] == 'g'){
                b += "c";
            }
            else{
                b += a[--i];
            }
        }
        else{
            b += a[i];
        }
    }
    return b;
}
string c2ng(string a){
    string b = "";
    for(int i = 0; i < a.size(); i++){
        if(a[i] == 'c'){
            b += "ng";
        }
        else{
            b += a[i];
        }
    }
    return b;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    l = vector<string>(n);
    for(int i = 0; i < n; i++){
        cin >> l[i];
        l[i] = ng2c(l[i]);
    }
    sort(l.begin(), l.end(), comp);
    

    for(int i = 0; i < n; i++){
        cout << c2ng(l[i]) << '\n';
    }
    return 0;
}