[백준 BOJ] 27466번 그래서 대회 이름 뭐로 하죠 (C++/cpp)

문제 설명

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

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

 

접근 방법 - 문자열에 대한 그리디 알고리즘 문제

백준의 27466번 문제는 문자열에 대한 그리디 알고리즘 기법을 활용하여 해결해야하는 문제이다.

해당 문제는, 주어진 문자열에 대해 운영진이 좋아할 만한 대회 이름을 만들 수 있는지를 출력해야하는 문제이다.

이때 운영진이 좋아할 대회 이름의 조건은 아래와 같다.

• 주어진 문자열에 대해, 0개 이상의 알파벳을 제거할 수 있다.
• 대회 이름의 길이는 M이어야 한다.
• 대회 이름의 맨 뒷 글자는 자음이어야 한다. (a, e, i, o, u를 제외한 알파벳)
• 뒤에서부터 2번째, 3번째 글자는 A이어야 한다.

필자와 같은 경우엔, 입력으로 주어지는 문자열을 뒤에서부터 탐색하며 조건에 맞게끔 대회 이름을 만들어나가도록 하였다.

이 원리대로면 대회 이름을 뒷 알파벳에서부터 하나씩 만들어나가야할 것인데, 정답을 출력할 때 문자열을 다시 역순으로 출력만 하면 되기 때문에 그렇게 복잡한 문제는 아니었다.

자세한 설명은 아래에 계속 기재하니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 주어지는 문자열의 총 길이(n)와 운영진이 원하는 대회 이름의 길이(k), 그리고 문자열(st)을 순차적으로 입력받는다.

숫자와 문자열 입력 간 충돌이 발생하지 않도록, 필자는 cin.ignore()를 사용하였다.

 

2) 대회 이름을 짓는 데에 사용할 벡터 s를 선언해둔다. 

 

3) st의 끝에서부터 처음까지 문자를 역순으로 탐색하는데, 반복문을 사용하여 아래의 연산을 취한다.

- 벡터 s가 비어있는 경우는 맨 뒷글자로 배정된 문자가 아직 아무것도 없음을 의미한다.

이때 st의 현재 위치 문자가 자음(a, o, i, e, u를 제외한 알파벳)이라면, s에 요소 삽입을 수행한다.

- 벡터 s의 크기가 1 또는 2인 경우는, 뒤에서부터 두번째 및 세번째 문자가 아직 배정되어있지 않음을 의미한다.

이때 st의 현재 위치 문자가 'A'라면, s에 요소 삽입을 수행한다.

- 벡터 s의 크기가 3 이상인 경우라면, 그 이후의 나머지 글자는 아무렇게나 배정하여도 좋다.

그렇기 때문에, st에 탐색할 글자가 아직 남아있다면 해당 글자를 s에 요소 삽입을 수행하도록 한다.

- 만약 벡터 s의 크기가 k와 동일하다면, 이는 대회 이름이 적절하게 완성되었음을 의미하기 때문에 break를 통하여 반복문을 종료하도록 한다.

 

4) 대회 이름이 규칙에 맞게 적절하게 완성되었는지를 확인해본다.

- 벡터 s의 크기가 k와 동일하지 않다면, 이는 대회 이름이 적절하게 완성되지 않았음을 뜻한다.

따라서 이 경우에는, "NO"를 출력하도록 한다.

- 다만 벡터 s의 크기가 k와 동일하다면, 이는 대회 이름이 적절하게 완성되었음을 뜻한다.

따라서 이 경우에는, "YES"를 출력하고 s에 있는 문자 요소들을 역순으로 하여 대회 이름을 적절하게 출력하도록 한다.

 

5) 정답을 출력하였다면, 즉시 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <string>
#include <vector>
#define endl '\n'
using namespace std;

//백준 27466번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);   cout.tie(NULL);

	int n, k;
	cin >> n >> k;
	cin.ignore();
	string st;
	cin >> st;

	vector<char> s;
	for (int i = st.length() - 1; i >= 0; i--) {
		if (s.empty() && !(st[i] == 'A' || st[i] == 'O' || st[i] == 'I' || st[i] == 'U' || st[i] == 'E')) {
			s.push_back(st[i]);
		}
		else if ((s.size() == 1 || s.size() == 2) && st[i] == 'A') {
			s.push_back(st[i]);
		}
		else if (s.size() >= 3) {
			s.push_back(st[i]);
		}

		if (s.size() == k) { break; }
	}

	if (s.size() != k) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
		for (int i = k - 1; i >= 0; i--) {
			cout << s[i];
		}
		cout << endl;
	}
}

 

제출 결과

(2023.07.21 백준 27466번 문제 제출 결과)