이 문제에서는 문자열 str과 Q개의 쿼리가 주어집니다. 각 쿼리는 하나의 숫자 X를 담고 있으며, 우리가 작성해야 할 프로그램은 사전순(lexicographical order)으로 X번째로 작은 부분 문자열을 찾아 응답하는 역할을 합니다.
문제 설명
각 쿼리에 대해 문자열의 모든 부분 문자열을 알파벳 순서대로 정렬했을 때 X번째 위치에 해당하는 부분 문자열을 구해야 합니다.
예시를 통해 문제를 살펴보겠습니다.
입력: str = "point"
Q = 4, query = {4, 7, 2, 13}
출력: n, oi, in, poin
설명
문자열 str의 모든 부분 문자열을 사전순으로 나열하면 다음과 같습니다.
i, in, int, n, nt, o, oi, oin, oint, p, po, poi, poin, point, t
- 4번째 부분 문자열 → n
- 7번째 부분 문자열 → oi
- 2번째 부분 문자열 → in
- 13번째 부분 문자열 → poin
해결 접근 방식
가장 단순한 해결 방법은 다음 세 단계로 정리할 수 있습니다.
- 주어진 문자열에서 만들 수 있는 모든 부분 문자열을 생성합니다.
- 생성된 부분 문자열들을 자료구조에 저장한 후 사전순(알파벳 순서)으로 정렬합니다.
- 각 쿼리의 X값에 대해 정렬된 자료구조에서 X번째 요소를 꺼내 출력합니다.
부분 문자열을 저장할 때는 벡터(vector)를 사용하면 간편합니다.
길이가 N인 문자열의 부분 문자열 개수는 N × (N + 1) / 2개입니다. 따라서 이 방식의 시간 복잡도는 부분 문자열 생성에 O(N²), 정렬까지 고려하면 대략 O(N³ log N)이 됩니다. 즉, 문자열 길이가 크지 않은 경우에 적합한 직관적인 풀이입니다.
구현 예시
#include <bits/stdc++.h>
using namespace std;
vector<string> substrings;
void find_SortSubstrings(string s) {
int len = s.size();
for (int i = 0; i < len; i++) {
string dup = "";
for (int j = i; j < len; j++) {
dup += s[j];
substrings.push_back(dup);
}
}
sort(substrings.begin(), substrings.end());
}
int main() {
string str = "point";
find_SortSubstrings(str);
int Q = 4;
int query[] = { 4, 7, 2, 13 };
for (int i = 0; i < Q; i++) {
cout << "Query " << (i + 1) << " : 사전순으로 " << query[i] << "번째로 작은 부분 문자열은 " << substrings[query[i] - 1] << endl;
}
return 0;
}
실행 결과
Query 1 : 사전순으로 4번째로 작은 부분 문자열은 n
Query 2 : 사전순으로 7번째로 작은 부분 문자열은 oi
Query 3 : 사전순으로 2번째로 작은 부분 문자열은 in
Query 4 : 사전순으로 13번째로 작은 부분 문자열은 poin
코드 설명
find_SortSubstrings()함수는 두 개의 중첩 반복문을 사용해 시작 인덱스 i와 끝 인덱스 j를 기준으로 가능한 모든 부분 문자열을 만들어 벡터에 저장합니다.- 저장이 끝나면 STL의
sort()함수를 호출해 부분 문자열들을 사전순으로 정렬합니다. main()함수에서는 각 쿼리의 X값에 대해 정렬된 벡터의 (X − 1)번째 원소를 출력합니다. 배열 인덱스는 0부터 시작하므로 1을 빼주는 것이 핵심입니다.
마무리
이처럼 모든 부분 문자열을 생성한 뒤 정렬만 하면, 임의의 X번째 부분 문자열 질의에 O(1) 시간에 바로 응답할 수 있습니다. 문자열이 짧고 쿼리가 많은 상황이라면 전처리 비용을 한 번만 지불하고 여러 쿼리를 효율적으로 처리할 수 있는 실용적인 접근 방식입니다.