[C++] 백준 16500번: 문자열 판별

🔗 문제

16500번: 문자열 판별

16500번: 문자열 판별

 

🖍 풀이

 

만든 예시 

softcorn
3
softc
corn
soft

S의 문자열 하나하나 A목록과 대조 시키며 풀면 된다.

 

 

 

idx	0	1	2	3	4	5	6	7
S	s	o	f	t	c	o	r	n
A[0]	s	o	f	t
A[1]	c	o	r	n
A[2]	s	o	f	t	c

s[0]의 s로 시작하는 단어가 있는지 A를 뒤지고

s[1]의 o로 시작하는 단어가 있는지 A를 뒤지고

… 이걸 s.size()만큼 반복한다.

 

---

이해가 잘 안 간다면? 

 

🔍 A[0]

S[4] 까지 일치하므로 조합 가능성이 있어보인다. S[5]부터 일치하는 문자열이 있는지 탐색해본다.

하지만 A 목록 중에 'o'로 시작하는 단어는 없기 때문에 문자열을 찾지 못한다. 'o'로 시작하는 단어를 뒤져봤으므로 visited[5] = true로 변경해준다. 

 

 

🔍 A[1]

첫문자부터 일치하지 않는다. 

 

 

🔍A[2]

S[0] ~ S[3]까지 일치하므로 조합 가능성이 있어보인다. S[4]부터 일치하는 문자열이 있는지 탐색해본다. 

A[1]에서 S[4]부터 일치하는 단어를 찾았다. 

 

 

---

소스 설명 

 

s[idx]로 시작하는 단어가 있으면 S를 idx 부터 idx + A.size()만큼 잘라낸다.

std::string tmp = S.substr(idx, idx + A.size())

 

잘라낸 단어가 A와 일치한다면 A는 S를 만들 가능성이 있다. 이제 S[idx + A.size()]부터 탐색을 하기 위해 재귀함수를 호출한다.

if(tmp == A[i])
{
    // S 조합 성공
    if(S.size() == (A[i].size() + idx))
    {
        std::cout << "1";
        exit(0);
        return;
    }
    // S[idx] 문자열을 뒤져봤다는 방문 표시를 하고 재귀 함수를 호출
    visited[idx] = true;
    combination(idx+ A[i].size());
}

 

시간 초과 피하는 방법

 

재귀함수가 불필요하게 돌면 시간 초과다.

bool DP[idx]로 S[idx]로 시작하는 단어를 탐색했었는지 판별해서 함수 호출 횟수를 줄일 수 있다.

if(visited[idx] == true)
    return;

 

 

💾  소스

#include <iostream>
#include <string>
#include <vector>
#define MAX 100

std::string S;
std::vector<std::string> A;
int N = 0;
bool visited[MAX+1];

void combination(const int idx)
{
    if(visited[idx] == true)
        return;
    
    for(int i=0; i<N; ++i)
    {
        std::string tmp = S.substr(idx, A[i].size());
        if(tmp == A[i])
        {
            visited[idx] = true;
            if(S.size() == (A[i].size() + idx))
            {
                std::cout << "1";
                exit(0);
                return;
            }
            combination(idx+ A[i].size());
        }
    }
    
    return;
}

int main()
{
    std::cin >> S >> N;
    A.resize(N);
    
    for(int i=0; i<N; ++i)
    {
        std::cin >> A[i];
    }
    
    combination(0);
    std::cout <<"0";

    return 0;
}