[BOJ 34803 // C++] 문자열 로또

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 34803번 문제인 문자열 로또이다.
문제는 아래 링크를 확인하자.

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

 

주어진 제한조건에서, 각 문자열에서 얻을 수 있는 길이 \(K\)의 부분문자열은 총 \(L-K+1\)개임을 관찰하자.

 

따라서 주어진 문제는 총 \(N(L-K+1)\)개의 부분문자열 중 가장 많이 등장한 문자열의 등장 횟수를 구하는 문제로 볼 수 있다.

 

모든 부분문자열의 길이는 100 이하이고 부분문자열의 총 개수는 2000 이하이므로, 정렬이나 map 등을 이용하여 각 각 부분문자열의 등장 횟수를 구해 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <map>
using namespace std;

int L, N, K, ans;
string s[20];
map<string, int> mp;

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

    cin >> L >> N;
    for (int i = 0; i < N; i++) cin >> s[i];
    cin >> K;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k + K <= L; k++) mp[s[i].substr(k, K)]++;
    }

    for (auto &p:mp) ans = max(ans, p.second);
    cout << ans;
}