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

문제링크 : https://www.acmicpc.net/problem/1599

1599번: 민식어

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

map<string, int> m{ {"a",1},{"b",2},{"k",3},{"d",4},{"e",5},{"g",6},{"h",7},
{"i",8},{"l",9},{"m",10},{"n",11},{"ng",12},{"o",13},{"p",14},{"r",15},{"s",16},
{"t",17},{"u",18},{"w",19},{"y",20} }; //민식어

bool cmp(vector<string>&a, vector<string>&b)
{
    for(int i=0; i<min(a.size(), b.size()); i++) //짧은 배열 기준 비교 (배열 범위 초과 방지)
    {
        if(m[a[i]] == m[b[i]]) continue;
        else return m[a[i]] < m[b[i]]; //민식어 기준으로 정렬
    }
    return a.size() < b.size(); //길이 짧은 배열이 우선
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N; string s;
    cin >> N;

    vector<vector<string>>v;
    vector<string>tmp;

    for(int i=0; i<N; i++)
    {
        tmp.clear();
        cin >> s;
        for(int j=0; j<s.size(); j++)
        {
            string temp = "";
            if(s[j] != 'n') 
            {
                temp+=s[j]; //하나씩 더해줌
                tmp.push_back(temp); 
            }
            else
            {
                if(s[j]=='n' && s[j+1] == 'g') //ng의 경우 (현재 n인데 다음이 g임)
                {
                    tmp.push_back("ng");
                    j++; //2글자니까 하나 건너뜀
                }
                else // n의 경우
                {
                    tmp.push_back("n");
                }
            }
        }

        v.push_back(tmp);
    }    

    sort(v.begin(), v.end(), cmp);

    for(int i=0; i<v.size(); i++)
    {
        for(auto str : v[i])
        {
            cout << str;
        }
        cout << "\n";
    }

    return 0;
}

아직도 싫어하는 문제열문제다.

민식어 기준으로 정렬을 해야하고, ng의 경우를 조심해야 한다.

n이 아닐 때는 현재 문자를 계속 더해주면서 문자열을 만들고 

n일 때는 다음 문자가 g인지 아닌지를 판별하여 ng를 더해줘야하는지 그냥 n을 더해줘야 하는지 체크를 해줘야 한다.

이는 그냥 문자열로 비교하면 ng가 아닌 n과 g로 보기 때문에 민식어의 {ng, 12} 구별이 불가능해져서 꼭 해야한다.

 

이후 정렬을 할 때 짧은 배열을 기준으로 비교해야 한다.

긴 배열을 기준으로 비교하면 빈 곳을 비교하는 경우가 생겨서 OutOfBounds 런타임 에러가 발생한다.

map을 이용해 민식어의 단어별 각 숫자 수치대로 정렬을 해주고, 길이가 짧은 배열을 우선으로 한다.