Level 1. 카드 뭉치

Level 1. 카드 뭉치

 

 

첫 번째 뭉치에서 단어를 발견할 경우 첫 번째 인덱스를 증가시키고, 두 번째 뭉치에서 발견할 경우 두 번째 인덱스를 증가시키며 마지막까지 확인하면 된다.

 

두 인덱스가 범위를 넘어가는 경우만 주의해주면 된다.

 

#include <iostream>
#include <vector>

using namespace std;

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal)
{
    int i = 0, j = 0;
    size_t nGoal = goal.size();
    size_t nCards1 = cards1.size(), nCards2 = cards2.size();

    while (i + j < nGoal)
        if (i < nCards1 && cards1[i] == goal[i + j])
            ++i;
        else if (j < nCards2 && cards2[j] == goal[i + j])
            ++j;
        else
            return "No";

    return "Yes";
}

 

다른 풀이를 찾아보니 DFS를 이용한 풀이도 있었다.

원풀이자가 함수 이름을 DFS라고 해서 나도 DFS라고 했다.

 

하지만, 경로와 목적지가 정해져 있고 모든 경로를 탐색하지 않고 조건에 따라 진행한다는 점에서 DFS보다는 일반 재귀에 가깝다고 생각한다.

 

#include <iostream>
#include <vector>

using namespace std;
using vsIterator = vector<string>::iterator;

string rDFS(vsIterator vsIt1, vsIterator vsIt2, vsIterator vsItGoal,
            vsIterator vsIt1End, vsIterator vsIt2End, vsIterator vsItGoalEnd)
{
    if (vsItGoal == vsItGoalEnd)
        return "Yes";

    if (vsIt1 != vsIt1End && *vsIt1 == *vsItGoal)
        return rDFS(++vsIt1, vsIt2, ++vsItGoal, vsIt1End, vsIt2End, vsItGoalEnd);
    else if (vsIt2 != vsIt2End && *vsIt2 == *vsItGoal)
        return rDFS(vsIt1, ++vsIt2, ++vsItGoal, vsIt1End, vsIt2End, vsItGoalEnd);
    else
        return "No";
}

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal)
{
    return rDFS(cards1.begin(), cards2.begin(), goal.begin(),
                cards1.end(), cards2.end(), goal.end());
}