[백준/C++] 1294번: 문자열 장식

문제 & 링크

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

 

풀이

1. 각 문자열을 원하는 대로 쪼갤 수 있기에, 각 문자열(string)의 맨 앞 문자(char) 끼리 비교하여 사전순으로 가장 앞서는 문자 하나를 가져온다.

2. 사전순으로 가장 앞서는 문자가 여러 문자열에 있을 경우 그 다음인 두 번째 문자도 고려해야 한다.

  - 문자열을 쪼개되, 조각의 순서는 유지해야 하는 조건

  - 문제의 출력 조건을 만족하기 위해서 뒤의 문자도 고려하여 해당 문자열의 맨 앞 문자 추출

  ex) CB, CA이렇게 두 문자열이 있을 경우 맨 앞 문자는 C로 사전순으로 같다. 그러면 두 번째 문자인 A와 B를 비교하여 두 번째 문자열에서 맨 앞 문자를 추출해야 한다. (이 경우 최종 결과 CACB, 만약 첫 번째 문자열에서 맨 앞 문자를 먼저 추출 시 CBCA)

3. 1번과 2번을 참고하여, 입력 받은 각 문자열끼리 정렬 후 사전순으로 가장 앞서는 문자열의 맨 앞 문자를 추출한다.

  - 우선순위 큐를 내림차순으로 이용, min heap

4. 우선순위 큐의 top인 문자열의 맨 앞 문자를 추출한 후 남은 문자열을 다시 우선순위 큐에 넣는다. 

  - 남은 문자열이 없을 경우 (size = 0) 무시

5. 예외 사항 고려

  ex) C, CA 이렇게 두 문자열이 있을 경우 C가 CA보다 사전순으로 앞서기에 우선순위 큐의 top은 C이다. 그런데 C라는 문자열에서 맨 앞 문자를 추출하면 최종 결과는 CCA가 된다. 하지만 CAC라는 사전순으로 앞서는 문자가 있음을 알 수 있다.

6. ASCII상으로 대문자보다 큰 값(ex. 소문자 'z')을 문자 맨 뒤에 붙이고, 4번에서 정한 size를 1이 되었을 때 무시하는 것으로 수정

  ex) Cz, CAz 이렇게 두 문자열이 있을 경우 CAz가 Cz보다 사전순으로 앞서기에 우선순위 큐의 top은 CAz이다. C, A를 순서대로 추출하고 z만 남을 경우 우선순위 큐에 넣지 않기에, 남는 문자열은 Cz이다. C를 추출하고 z만 남기에 우선순위 큐에 넣지 않는다. 이에 최종 결과는 CAC로 원하는 결과를 얻게 되었다.

 

코드

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int main() {
    priority_queue<string, vector<string>, greater<string>> pq;

    int N;
    cin >> N;

    string input_str;
    for (int i = 0; i < N; i++) {
        cin >> input_str;
        pq.push(input_str + "z");
    }

    while (!pq.empty()) {
        string str = pq.top();
        pq.pop();

        cout << str[0]; // 맨 앞 문자 출력

        str = str.substr(1); // 맨 앞 문자 제거

        if (str.size() > 1) { // 추가로 붙인 z를 제외하고 공백 문자열이 아닐 경우
            pq.push(str);
        }
    }
}