개요

[링크]백준 16500번: 문자열 판별

• 입력
  첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

• 출력
  A에 포함된 문자열로 S를 만들 수 있으면 1, 없으면 0을 출력한다.

접근 방식

• 처음 시도한 방법은

  //S의 n-1번째 문자열까지 채워진 상태, s의 몇번째 문자부터 시작하는지 커서값
  void solution(int n,int cursor)

  이렇게 재귀 함수를 세운 후, 반복문으로 모든 입력문자열과
  S를 비교하는 방법으로 생각을 했다.
  다이나믹 프로그래밍방식으로 풀지 않아 시간초과가 난 방법이다.

  temp라는 string형 변수를 선언해준 뒤
  각 입력문자열의 길이만큼 S의 문자를 temp에 넣어준 후 비교를 하였다.

  맞닥뜨린 첫 번째 반례는 입력문자열중에 한 문자열이 남은 S의 길이보다
  길 때 S의 범위를 넘어가는 값을 참조하려해서 오류가 났다.
  ->조건문 if(cursor+j<S.length()) 이 부분 해결

  두번째 반례는 예를 들어 S가 aab이고 문자열값이 각각 a,ab일 때
  오류가 난다.
  모든 경우의 수로 짜지않고 그리디방식으로 a를 넣으면 그다음 것만 고려를 하게 짜서 a들어오고 또 a들어와서 b를 못넣어서 0을 배출했다.

  그래서 모든 경우의 수를 고려하게 짰더니 시간초과가 떴다.
  답이 1일땐 모든 함수에서 return하게 짰지만 시간초과가 계속 떠서
  생각해보니 1인 경우가 없거나 마지막에 있을 땐 빠져나오는 경우가 없어서 시간초과가 났었다.
  

• 두 번째 방법은
  [kks227님의 깃허브] 를 본 후 공부 해본 다이나믹 프로그래밍을 활용한 방법인데
  내가 푼 방식과 비슷하지만 dp배열을 통해 한번 방문한 함수는 빠르게 넘어갈 수 있어서 시간초과가 나지 않는다.

  //n번째 문자까지 S와 매칭 시켰을 때 나머지 문자열과 S를 맞출 수 있는 지 bool형 반환 하는 함수
  bool word(int n) 

  이렇게 재귀 함수를 짰다.

  이 방식에선 string의 []연산자를 이용해 문자열의 각 char형 원소들을 비교해서 cursor을 굳이 안써도 된다는 점이 좋고,

  재귀를 빠져나올 때 ret=0과 비교를 하게되는데
  다른 다이나믹프로그래밍 처럼 max를 이용하지않고
  bool형이라 |= 연산자를 이용하면 하나라도 1이면 ret에 1이 저장된다.

  //|=을 이용해 만약 1이 나온다면 1 아니면 0으로 ret을 설정하게끔
  if (flag) ret |= word(n + inputArr[i].length());

  첫 번째 코드(시간 초과)

#include<iostream>	
#include<vector>
#include<string.h>
#include<memory.h>

//처음에 시도방법은 cursor의 위치에서 부터 temp string형변수에 다음 string을 넣어준 후 S의 커서위치부터 temp변수 길이만큼 할당한 후 비교하는 방법인데
//중간에 temp변수가 s보다 커버리게되면 nullreference라 오류걸린다.
//다음 반례 s가 aab이고 a, ab가 들어오면 a를처리후 a가 맞으므로 a를 또 처리함 처리하자
//시간초과 남
using namespace std;
const int MAX = 100;

vector<string> inputArr;
string S;
int amount = 0,ans=2;

void input() {
	string temp=" ";
	cin >> S;
	cin >> amount;

	for (int i = 0; i < amount; i++) {
		cin >> temp;
		inputArr.push_back(temp);
	}
}

//S의 n-1번째 문자열까지 채워진 상태, s의 몇번째 문자부터 시작하는지 커서값
void solution(int n,int cursor) {
	if (ans == 1) return;
	bool isThereAnswer = false;
	
	//n번째 문자열
	string temp = "";
	if (cursor==S.length()) {
		ans = 1;
		return;
	}
	else if (cursor > S.length()) {
		ans = 0;
		return;
	}

	for (int i = 0; i < amount; i++) {
		if (ans == 1) return;
		//초기화
		temp = "";
		for (int j = 0; j < inputArr[i].length(); j++)
		{
			if(cursor+j<S.length())
			temp += S[cursor + j];
		}
		//만약 문자열중에 같은게 있을 때
		if (!strcmp(temp.c_str(), inputArr[i].c_str())) {
			isThereAnswer = true;
			solution(n + 1, cursor + inputArr[i].length());
			if (ans == 1) return;
		}
	}
		//문자열중에 같은게 없을때는 0반환
	if (ans!=1 && !isThereAnswer)
		ans = 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	input();
	solution(0,0);
	cout << ans;
}

두번째 코드(답)

#include<iostream>
#include<memory.h>

using namespace std;

//L이 S의 길이, 갯수 amount , dp배열
int L, amount, dp[101];
//S문자열, 입력문자열 받는 배열
string S,inputArr[101];

void input() {
	cin >> S >> amount;
	for (int i = 0; i < amount; i++) {
		cin >> inputArr[i];
	}
	L = S.length();
	//dp -1로초기화
	memset(dp, -1, sizeof(dp));
}

//n번째 문자까지 매칭 시켰을 때 남은 문자들도 맞출 수 있는 지 bool형 반환 하는 함수
bool word(int n) {
	int& ret = dp[n];
	if (ret != -1) return ret;
	if (n == L) return ret = 1;

	ret = 0;

	for (int i = 0; i < amount; i++) {
		//S의 남은 길이보다 문자열값이 더 길면 패스해야함
		if (L < n + inputArr[i].length()) continue;
		//각 문자열과 S 비교했을때 같으면 true로 바뀌는 bool형 변수
		bool flag = true;
		//string의 []연산자를 써써 각 문자를 비교 이방식으로 하면 cursor가 필요없음
		for (int j = 0; j < inputArr[i].length(); j++) {
        	//n부터 n+j까지의 S문자열과 inputArr[i]비교해서 다르면 flag=false
			if (S[n + j] != inputArr[i][j]) flag = false;
		}

		//|=을 이용해 만약 재귀중 return값이 1이 나온다면 ret= 1 아니면 0
		if (flag) ret |= word(n + inputArr[i].length());
		
	}
	return ret;


}

int main() {
	input();
	bool ans = word(0);
	cout << ans;
}

문풀후생

첫번째 방식에서 ans를 잘 활용해서 1이면 모든 함수를 빠져나온다는 생각했을 때 dp를 사용안해도되겠다고 생각해서 그렇게 구현했지만

1이 아니면 계속 호출될수도 있다는 부분을 나중에서야 깨달았다.

시간을 많이 투자하긴 했지만 그래도 인터넷을 뒤지며 얻은게 좀 많은 문제였다.

flag변수를 이용해 ret값을 정해주는 스타일이라던지 |=을 이용해 bool형들을 비교하는 생각이라던지 많이 배운 문제였다.

레퍼런스

[kks227님의 깃허브]