[백준 9081] 단어 맞추기 (C++)

📕문제

---

BEER라는 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬하게 되면

BEER
BERE
BREE
EBER
EBRE
EEBR
EERB
ERBE
EREB
RBEE
REBE
REEB

와 같이 된다. 이러한 순서에서 BEER 다음에 오는 단어는 BERE가 된다. 이와 같이 단어를 주면 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하시오.

📕입력

---

입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알파벳으로 이루어진다. 단어의 길이는 100을 넘지 않는다.

📕출력

---

각 테스트 케이스에 대해서 주어진 단어 바로 다음에 나타나는 단어를 한 줄에 하나씩 출력하시오. 만일 주어진 단어가 마지막 단어이라면 그냥 주어진 단어를 출력한다.

 

🔎문제 해석

---

일단 틀렸습니다. 50%까지 가다가 틀렸다는 멘트가 나올 때마다 제 심장이 찢어지더군요.

일단 c++ 에는 조합을 자동으로 구해주는 permutation기능이 있지만, 저는 permutation을 쓰지 않고 문제를 풀고 싶어서 고집을 부렸습니다.

permutation이란?

위 링크를 들어가면 자세한 permutation을 알 수 있습니다. c++ 라이브러리 중에서 꽤 자주 사용되는 라이브러리인 거 같습니다.

하지만 저는! 이걸 쓰지 않고 문제를 풀고 싶었습니다.

물론 그 처참한 결과가 위의 사진이지만...

저는 HELLO가 있다면 사전 순으로 바꿔줄수있는 위치를 찾았습니다.

문자열의 역순으로 아스키코드를 비교해서 아스키코드가 작아지는 기준점을 구해줬습니다.

💡왜 작아지는 지점을 구하느냐?

사전순으로 정렬될 때는 아스키코드가 점점 커지는 순으로 정렬되기 때문입니다.

CBA를 예로 들자면 CBA는 A에서 출발해서 아스키코드를 비교할 때 작아지는 지점이 없습니다.

즉 CBA는 사전 순으로 마지막이라는 뜻입니다.

 

"HELLO"에서는 이제 HELL(여기) O가 기준점이 될 겁니다.  O -> L로 갈 때 아스키코드가 작아지기 때문이죠.

그러면 이제 그 전까지의 문자열은 그대로 저장해주고, 해당 기준점에서부터 문자열을 바꿔주는 겁니다.

기준점으로 교체해주는 알파벳은 원래 기존의 알파벳보다 사전 순으로 뒤에 있어야 하기에 아스키코드값이 커야 하고, 사전 바로 다음에 와야 하기 때문에 큰 값들 중에서 최솟값이어야 합니다.

💡즉! 기존 자리에 알파벳보다 뒤에 있는 알파벳 이어야 하고, 가장 가까운 알파벳이어야 합니다.

 

자 이렇게 말하면 분명히 이해하기 어려우실 거 같아서 이해하기 쉽게 그림으로 설명해드리겠습니다.

우리가 원하는 것은 아스키코드가 작아지는 지점입니다. 즉 U->H로 넘어갈 때 아스키코드가 작아집니다.

그럼 이제 우리는 저 기준점인 H부터 알파벳이 몇 번 들어가는지를 기록해줘야 합니다.

사전 순으로 기록해주는 것이 편하겠죠? (당연한 겁니다)

E : 1, H : 1 ,  L : 1 , T : 2 , U : 1번 등장하게 됩니다.

그럼 H에 올 수 있는 알파벳은 E와 H를 제외하고 모든 알파벳이 올 수 있습니다. 하지만 사전 바로 다음에 오는 알파벳을 구해야 하기에 H와 가장 가까운 L이 H의 자리에 들어가게 될 것입니다.

 

S L ○ ○ ○ ○ ○ 이제 나머지 자리에 들어가는 알파벳들은 이제 사전 순으로 앞에 오는 알파벳들을 순서대로 넣어주면 됩니다.

그럼 SHUTTLE 다음으로 오는 알파벳은 SLEHTTU가 될 겁니다.

 

⚡의외로 간단한 해결방법

---

나는 문자열을 입력받고-> 그 문자열에 대한 답을 출력하는 형식으로 진행했는데 

문자열에 대한 모든 답을 vector에 저장하고 그 vector에 있는 문자열들을 한꺼번에 출력하니까 문제가 풀렸다. 

진짜 어이가 없다. 출력형식은 똑같은데 왜일까? 진짜 알수없음!!

💻코드

/*
백준 실버1 단어맞추기
해당 단어가 있으면 그 단어 다음에 바로 오는 단어를 출력
해당 단어가 마지막이면 그 단어를 출력

*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
int n;
vector<int> eng;
vector<string> result;
int check(string str);
int main()
{
    cin >> n;
    eng.resize(26, 0);
    for (int i = 0; i < n; i++)
    {
        string str;
        string answer;
        cin >> str;
        int idx = check(str);
        if (idx == -1)
        {
            result.push_back(str);
            continue;
        }
        for (int x = 0; x < idx; x++)
        {
            answer += str[x];
        }
        for (int j = idx; j < str.length(); j++)
        {
            eng[str[j] - 65]++;
        }
        int cur = 9999;
        //해당 idx의 알파벳보다 제일 가까운 큰수를 idx자리에 넣고 그 자리 뒤부터는 작은순서대로 쫘좌작 넣기.
        for (int k = idx; k < str.length(); k++)
        {
            if (eng[str[k] - 65] == 0) //해당 알파벳이 한번이라도 나와야하고.
                continue;
            if (str[k] > str[idx])
            {
                if (cur > str[k])
                {
                    cur = str[k];
                }
            }
        }
        answer += cur;
        eng[cur - 65]--;
        for (int y = 0; y < 26; y++)
        {
            if (eng[y] == 0)
            {
                continue; 
            }
            while (eng[y] != 0)
            {
                answer += y + 65;
                eng[y]--;
            }
        }
        result.push_back(answer);
    }
    for(auto a : result){
        cout<<a<<endl;
    }
}
int check(string str) //갈수록 아스키코드가 커져야함. 작아지는 구간이 있으면 거기서부터 바꿔줄수있음.
{
    int num = 0;
    int res = 0;
    for (int i = str.length() - 1; i >= 0; i--)
    {
        if (num <= str[i])
        {
            num = str[i];
        }
        else
        {
            return i;
        }
    }
    return -1;
}

✔느낀 점

• 어이가 없다.
• 출력형식으로 억까당했다.
• 개빡친다.