Boj 15440) Vera And Lcs

문제

백준 15440

lcs 최솟값

어떤 문자열 S 와 임의의 문자열 간의 lcs 는 S 에서 등장하는 문자의 빈도 중 최솟값보다 같거나 크다.

예를들어 가능한 문자의 집합 {a, b, c} 에서 S 가 "aabbbc" 라면 lcs 의 최솟값은 c 의 빈도 수인 1 이 된다.

이에 대한 증명은 다음과 같다.

임의의 문자열 S 가 있고 여기서 문자의 빈도 중에 가장 작은 것을 \(a\) 라고 하자. 그리고 임의의 문자열 S' 가 있고 여기서 문자의 빈도 중 가장 큰 것을 \(b\) 라고 하자.

S 에서의 어떤 문자든 그 빈도는 \(a\) 보다 크거나 같다. 따라서 S 에서 \(b\) 에 해당하는 문자의 빈도 역시 \(a\) 보다 크거나 같다.

그러므로 \(b\) 에 해당하는 문자는 S 와 S' 에 \(a\) 이상 존재한다.

증명 끝.

구성

답을 구성하는 방법은 간단하다.

1. 가장 적은 빈도의 문자로 문자열을 채운다.
2. lcs - 최소빈도 만큼 원래 문자와 다른 문자를 원래 문자로 바꾼다.

시간 복잡도

= \(O(N)\)

코드

int alpcheck[255];

int main()
{
    string s;
    int n, k;
    cin >> n >> k >> s;

    for (auto c : s) alpcheck[c]++;
    int* m = min_element(alpcheck + 'a', alpcheck + 'z' + 1);

    if (n < k || *m > k)
    {
        cout << "WRONGANSWER";
        return 0;
    }

    k -= *m;
    string ans = string(n, m-alpcheck);
    for (int i = 0; i < n && k; i++)
        if (ans[i] != s[i])
        {
            ans[i] = s[i];
            k--;
        }

    cout << ans;
}