[백준 24524번} 아름다운 문자열 (C++)

문제링크 : https://www.acmicpc.net/problem/24524

24524번: 아름다운 문자열

 

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

string s, t;
vector<int>arr;

int main()
{
	fastio;
	cin >> s >> t;
	arr.resize(t.size());  //문자열 t의 크기로 리사이즈
	for (int i = 0; i < s.size(); i++)
	{
		for (int j = 0; j < t.size(); j++)
		{
			if (s[i] == t[j])  
			{
				if (j == 0)    //문자열 t의 첫 문자가 같으면
				{
					arr[j]++;  //해당 문자 카운트
				}
				else if (arr[j] < arr[j - 1])  //지금 문자의 갯수가 그전 문자의 갯수보다 적으면
				{ 
					arr[j]++;                  //전 문자의 갯수 카운트
				}
			}
		}
	}
	cout << arr[t.size() - 1];  //마지막 값 출력
	return 0;
}

아름다운 문자열 t의 각각의 문자 갯수를 저장하기 위한 벡터를 선언했다.

이때 벡터의 크기는 t의 길이일수밖에 없으므로 t의 길이로 리사이즈했다.

처음 문자가 같을 때 즉, j 값이 0일 때 t와 s의 문자열이 같다면 해당 벡터의 값(arr[0])을 증가시킨다.

만약 arr[j] < arr[j-1] 일때 (현재 문자의 갯수가 그전 문자의 갯수보다 적다면) 해당 벡터의 값(arr[j])를 증가시킨다.

 

아래 입력 예제를 보면

abba
ab

- 문자열 s의 첫 번째 문자 a의 경우

처음에 첫번째 문자인 a가 같으므로 arr[0]을 증가시킨다. (arr[0] = 1)

그다음 두번째 문자인 b의 경우는 그전 문자의 갯수가 0이고 현재 문자인 b의 갯수는 0이므로 지금 문자 b를 증가시킨다. (arr[1] = 1)

 

- 문자열 s의 두 번째 문자 b의 경우

어떠한 조건도 만족시키지 않으므로 넘긴다. (문자열 t의 각각의 문자 갯수는 현재 1인 상태)

 

- 문자열 s의 세 번째 문자 b의 경우

마찬가지로 어떠한 조건도 만족시키지 않으므로 넘긴다.  (문자열 t의 각각의 문자 갯수는 현재 1인 상태)

 

- 문자열 s의 마지막 문자 a의 경우

문자열 t의 첫번째 문자 a와 일치하므로 arr[0]을 증가시켜서 arr[0]의 값은 2가된다.

b의 경우는 일치하지않으므로 벡터 arr의 값은 최종적으로 2, 1이 된다.

 

여기서 각 배열의 값이 전부 같아야 성공적으로 문자열이 완성된다.

위의 경우는 ab를 한개 만들고 a가 남는 상태이다.

따라서 출력은 완성된 문자열의 갯수라고 할 수 있는 벡터 arr의 마지막 값을 출력한다.