백준 29198번 [이번에는 C번이 문자열](C++) -yes6686- 티스토리

백준 문제 풀이: 29198 [이번에는 C번이 문자열]

---

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

문제 설명:

n개의 문자열이 주어집니다. 각 문자열을 정렬하고, 이 중에서 k개의 사전순으로 앞선 문자열들을 선택합니다. 선택된 문자열들을 합친 후, 결과 문자열을 사전순으로 정렬하여 출력하는 문제입니다.

---

문제 해결 코드

// 이번에는 C번이 문자열 문제 해결 코드
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string s[301]; // 입력 문자열 저장 배열

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

    int n, m, k;
    cin >> n >> m >> k;

    // 각 문자열을 정렬
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        sort(s[i].begin(), s[i].end());
    }

    // 문자열 배열을 사전순으로 정렬
    sort(s, s + n);

    // 사전순으로 앞선 k개의 문자열을 합치기
    string result = "";
    for (int i = 0; i < k; i++) {
        result += s[i];
    }

    // 결과 문자열을 사전순으로 정렬
    sort(result.begin(), result.end());

    // 최종 결과 출력
    cout << result << '\n';

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘:
  • 각 문자열을 정렬하여 사전순으로 가장 작은 형태로 변환합니다.
  • 문자열 배열을 전체적으로 정렬하여, 사전순으로 앞선 k개의 문자열을 선택합니다.
  • 선택된 문자열들을 합친 후, 최종적으로 합쳐진 문자열을 다시 정렬합니다.
• 구현 세부사항:
  • s[i]: 각 문자열을 저장하는 배열입니다.
  • 문자열을 정렬하고, k개의 문자열을 합친 후 최종 정렬을 수행합니다.
  • 정렬은 STL의 sort를 사용하여 간단히 구현했습니다.
• 시간 복잡도 분석:
  • 각 문자열 정렬: O(n ⋅ m log m), 여기서 m은 문자열의 평균 길이.
  • 전체 문자열 배열 정렬: O(n ⋅ m log n).
  • 최종 결과 문자열 정렬: O(k ⋅ m log(k ⋅ m)).
  • 전체 시간 복잡도: O(n ⋅ m log m + n ⋅ m log n + k ⋅ m log(k ⋅ m)).

---

결과

이 알고리즘은 주어진 조건에 따라 문자열을 정렬하고, 사전순으로 가장 앞선 k개의 문자열을 선택하여 최종 결과를 출력합니다. 예를 들어:

• 입력:

          4 3 2
          cab
          abc
          bca
          bac
          

• 출력: aaaaabbbccc

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!