[C++][백준 32627] 문자열 줄이기

문제

접근 방법

a~z는 인덱스로 표현할 수 있다. a~z에 a를 뺄 시 0~25의 값을 가진다.
이를 활용하면 각 알파벳의 개수를 구할 수 있고 가장 앞서는 문자를 몇 개 지워야 할지도 계산할 수 있다.

코드

#include <iostream>
using namespace std;
int N, M, cnt[26], skipCnt[26];
string S, answer;

void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >> S;
    for (const char &c : S)
    {
        ++cnt[c - 'a'];
    }

    for (int i = 0; i < 26; ++i)
    {
        if (cnt[i] > M)
        {
            skipCnt[i] = M;
            break;
        }
        else
        {
            skipCnt[i] = cnt[i];
            M -= cnt[i];
        }
    }
}

void solve()
{
    for (const char &c : S)
    {
        if (skipCnt[c - 'a']-- > 0)
        {
            continue;
        }

        answer += c;
    }
    cout << answer;
}

int main()
{
    input();
    solve();
    return 0;
}

풀이

백준 대회 문제는 생각보다 높은 순위를 가지기 쉬운 것 같다. (다른 분들은 빠르게 푸는 걸 목표로 하셔서 그런 거 같기도 하다)

a~z의 개수를 구한 뒤 a부터 z까지 차례대로 몇 개를 스킵 해야 하는지 기록해 주면 된다.
M의 개수가 크거나 같으면 해당 문자 전체를 무시해야 하고 M의 개수보다 작다면 남은 문자만큼만 무시하면 된다.