[PS][구현] BOJ 17480 : 개구쟁이 준석이

[2021년 08월 14일 21시 28분 작성]

[PS][구현] BOJ 17480 : 개구쟁이 준석이

---

[문제 링크 : 클릭]

---

1. 풀이

 

구현하기 상당히 까다로운 문제입니다.

 

순서는 다음과 같습니다.

 

1. 문자열의 길이가 최대 14이기 때문에, 모든 부분 문자열에 대해 알파벳 개수 일치 여부를 탐색합니다. (Brute-Force) 2. 우선 반을 나눕니다. (길이가 홀수라면, mid값을 조정하여 1회 더 나눕니다) 3. 나누고 나서, 오른쪽 / 왼쪽 둘 중 하나를 골라 뒤집은 다음, 반대쪽 부분을 선택하여 2로 계속 진행합니다.     ㄴ> 만약, 반대쪽 부분의 길이가 1이라면, 해당 문자열을 체크합니다.

 

mid 값에 유의해서 코드를 전개해주면 해결할 수 있습니다 :)

 

 

---

2. 소스코드

[Github 링크 : 클릭]

#include <bits/stdc++.h>
using namespace std;

typedef unordered_set<string> uset;

string str; uset check;
int n, cnt[26], ans=0;

string GetRevStr(string s, int a, int b) // s[a, b]의 뒤집힌 문자열을 반환
{
	reverse(s.begin()+a, s.begin()+b+1);
	return s;
}

void MakeString(string curr, int a, int b)
{
	int mid = (a+b)/2, len = b-a+1;

	if(a >= b)
	{
		if(!check.count(curr)) //만약 만든 문자열이 처음 만든거라면? 
		{
			check.insert(curr); //중복 방지 체크!
			ans++; //카운팅
		}
		return;
	}

	for(int i=0; i<2; i++)
	{
		if(a <= mid-i) //왼쪽 부분을 뒤집고, 오른쪽 부분을 진행
			MakeString(GetRevStr(curr, a, mid-i), mid-i+1, b);
	
		if(mid-i+1 <= b) //오른쪽 부분을 뒤집고, 왼쪽 부분을 진행
			MakeString(GetRevStr(curr, mid-i+1, b), a, mid-i);

		if(len%2==0) break; //길이가 짝수이면, 반으로 나누는 경우는 1가지
	}	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin>>n;
	for(int i=0; i<n; i++)
	{
		char c; int k;
		cin>>c>>k;
		cnt[c-'a'] = k;
	}

	cin>>str;
	for(int i=0; i<str.size(); i++)
	{
		for(int j=0; (i+j)<=str.size(); j++) 
		{
			string s = str.substr(i, j);
			vector<int> tmp(26, 0);
			for(auto &c : s)
				tmp[c-'a']++;

			bool flag = false;
			for(int k=0; k<26; k++)
				if(cnt[k]!=tmp[k])
					flag = true;
			
			if(flag) continue; //만약, 해당 부분 문자열이 조건에 맞지 않는다면 계속..

			MakeString(s, 0, j-1); //조건(알파벳 개수 일치)에 맞는다면 문자열들을 탐색
		}
	}

	cout<<ans<<'\n';

	return 0;	
}

---

3. 복기

- 이렇게 조건이 까다롭고, 본문이 긴 문제는 차근차근 풀어볼 것