그래서 대회 이름 뭐로 하죠 (feat. 백준, 27466번)

그래서 대회 이름 뭐로 하죠
https://www.acmicpc.net/problem/27466

27466번: 그래서 대회 이름 뭐로 하죠

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
using namespace std;
int N, M;
string str;
bool func(register int idx, register int num, register int remove){
    if(remove == N - M){
        register int t = 1;
        for(register int i = str.size() - 1; i >= 0; --i){
            if(str.at(i) == '!')
                continue;
            if(t == 1){
                if(str.at(i) != 'A' && str.at(i) != 'E' && str.at(i) != 'I' && str.at(i) != 'O' && str.at(i) != 'U')
                    ++t;
                else
                    return false;    
            }
            else if(t <= 3){
                if(str.at(i) == 'A')
                    ++t;
                else
                    return false;
            }
            if(t > 3)
                return true;
        }
    }
    if(num == 1){
        if(str.at(idx) != 'A' && str.at(idx) != 'E' && str.at(idx) != 'I' && str.at(idx) != 'O' && str.at(idx) != 'U')
            return func(idx - 1, num + 1, remove);
        else{
            str.at(idx) = '!';
            return func(idx - 1, num, remove + 1);
        }
    }
    else if(num <= 3){
		if(str.at(idx)  == 'A')
            return func(idx - 1, num + 1, remove);
		else {
			str.at(idx)  = '!';
			return func(idx - 1, num, remove + 1);
		}
	}
	else{
		str.at(idx)  = '!';
		return func(idx - 1, num, remove + 1);
	}
    return true;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N >> M >> str;
    if(func(str.size() - 1, 1, 0)){
        cout << "YES\n";
        for(auto& ch : str){
            if(ch == '!')
                continue;
            cout << ch;
        }
    }
    else
        cout << "NO";
    return 0;
}
// *&)*@*

 

반응형

문자열의 뒤에서부터 체크하며 가능한 문자만 남기는 방식으로 풀이하였습니다.

불가능한 문자는 삭제하진 않고 '!' 로 치환하여 출력을 하지 않는 방향으로 풀이했습니다. (문자열을 삭제하면 그만큼 시간 소비가 발생하니까요.)