백준 11656번 [접미사 배열](C++) -yes6686- 티스토리

백준 문제 풀이: 11656 (접미사 배열)

---

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

문제 설명:

문자열 S가 주어졌을 때, 문자열의 **모든 접미사**를 사전 순으로 정렬하여 출력하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

    string s;
    cin >> s;

    vector suffixes; // 접미사를 저장할 벡터

    // 문자열의 모든 접미사 생성
    for (int i = 0; i < s.size(); i++) {
        suffixes.push_back(s.substr(i)); // i번째부터 끝까지의 접미사
    }

    // 접미사들을 사전 순으로 정렬
    sort(suffixes.begin(), suffixes.end());

    // 결과 출력
    for (const string &suffix : suffixes) {
        cout << suffix << '\n';
    }

    return 0;
}

---

코드 설명

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

• 핵심 알고리즘: 문자열의 접미사를 모두 생성한 뒤, 이를 사전 순으로 정렬합니다.
• 구현 세부사항:
  • s.substr(i): 문자열의 i번째 인덱스부터 끝까지의 접미사를 추출합니다.
  • sort(): 접미사들을 사전 순으로 정렬합니다.
• 시간 복잡도 분석:
  • 접미사를 생성하는 데 O(n)이 걸립니다.
  • 정렬의 시간 복잡도는 O(n log n)이며, 각 접미사의 길이가 O(n)이므로 총 시간 복잡도는 O(n² log n)입니다.

---

결과

주어진 문자열의 모든 접미사를 사전 순으로 출력합니다.

• 입력 예시:

  baekjoon

• 출력 예시:

  aekjoon  
  akjoon  
  baekjoon  
  ekjoon  
  joon  
  kjoon  
  oon  
  oon

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