프로그래머스 (C/C++) 133499 : 옹알이 (2)

https://school.programmers.co.kr/learn/courses/30/lessons/133499#

프로그래머스

 

---

풀이

dp + 메모이제이션으로 풀었다.

문자열 babbling의 인덱스를 하나씩 옮겨가며 해당 위치에서 옹알이에 일치하는 단어가 있는지 확인하고, 있다면 check 배열을 true로 바꿔준다.

check 배열이 true라면 해당 위치까지는 옹알이 배열에 있는 문자열로 이루어져 있다는 뜻이므로, 그 자리부터 옹알이 배열을 탐색한다면 결국 전체 문자열이 옹알이 배열에 있는 문자열로 이루어져 있음을 의미한다.

 

아래 링크의 문제는 해당 문제의 알고리즘과 동일한 문제와 그에 대한 풀이이므로 참고하면 좋을 듯 하다.

 

https://hwooo.tistory.com/291

LeetCode (C/C++) 139. Word Break

---

코드

#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

string dup[4] = {"ayaaya", "yeye", "woowoo", "mama"};
string S[4] = {"aya", "ye", "woo", "ma"};

int checkS(string s) {
    
    // 연속해서 같은 문자열을 포함하는 경우를 먼저 확인, 에러 처리
    for(int i = 0; i < 4; i++) {
        if (s.substr(0, dup[i].size()) == dup[i]) {
            return -1;
        }
    }
    
    // 주어진 문자열에 포함된 문자열이라면 해당 문자열의 길이 반환
    for(int i = 0; i < 4; i++) {
        if (s.substr(0, S[i].size()) == S[i]) {
            return S[i].size();
        }
    }
    return -1;
}

int solution(vector<string> babbling) {
    int answer = 0;
    int check[31];

    for (int i = 0; i < babbling.size(); i++) {
        
        fill(check, check + 31, false); 
        check[0] = true;
        
        for(int j = 0; j < babbling[i].size(); j++) {
            
            // 현재 위치까지 주어진 문자열로 표현 가능하다면
            if (check[j]) {
                
                // 현재 위치부터 주어진 문자열로 표현 가능한지 탐색
                int findLoc = checkS(babbling[i].substr(j));
                
                // 동일하다고 판단된 문자열이 끝나는 위치에 flag 세움
                if (findLoc >= 0) 
                    check[j + findLoc] = true;
            }
        }
        
        // 문자열을 끝까지 탐색했을 때 마지막 위치가 true라면 해당 문자열은 주어진 문자열들로만 표현 가능, answer++;
        if (check[babbling[i].size()] == true)
            answer++;
    }
    return answer;
}