코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.
원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
한 번 사용한 카드는 다시 사용할 수 없습니다.
카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.
예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.
문자열로 이루어진 배열cards1
,cards2
와 원하는 단어 배열goal
이 매개변수로 주어질 때,cards1
과cards2
에 적힌 단어들로goal
를 만들 수 있다면"Yes"
를, 만들 수 없다면"No"
를 return하는solution
함수를 완성해주세요.
cards1
의 길이, cards2
의 길이 ≤ 10cards1[i]
의 길이, cards2[i]
의 길이 ≤ 10cards1
과 cards2
에는 서로 다른 단어만 존재합니다.goal
의 길이 ≤ cards1
의 길이 + cards2
의 길이goal[i]
의 길이 ≤ 10goal
의 원소는 cards1
과 cards2
의 원소들로만 이루어져 있습니다.cards1
, cards2
, goal
의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.cards1
과 cards2
에 대한 index 를 다루기 위해 각각 c1_idx
, c2_idx
라는 변수를 할당해 주었다.
이후 goal
과 하나씩 비교하면서 각 인덱스 변수의 값을 증가 해 주는 방식으로 진행하였다.
goal
= ["i", "want", "to", "drink", "water"] 이라고 가정하자.c1_idx
와 c2_idx
는 모두 0
으로 처음에 초기화 해주면 아래와 같다.
다음과 같은 조건으로 탐색하였다.
1. c1_idx 는 cards1 의 size() 보다 작아야 한다.
2. c2_idx 는 cards2 의 size() 보다 작아야 한다.
3. 만약 1, 2가 모두 False 이면서 goal의 값들을 전부 탐색하지 못하였다면 "No"를 return
goal
의 index를 i
라 했을때, i
= 0일때 cards1
의 c1_idx
값이 goal[i]
와 같기 때문에 c1_idx
의 값을 키워준다.
그렇게 하면 위와 같이 index가 변화함을 알 수 있다.
이후 goal[i]
는 cards2
의 c2_idx
번째 값과 같기 때문에 c2_idx
의 값을 키워준다.
그렇다면 위와 같은 결과를 얻게 된다.
이러한 방식을 반복하여 i
가 goal
의 size() 값과 같으면 while
문을 종료한다.
#include <string>
#include <vector>
#include <iostream>
using namespace std;
string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
string answer = "No";
int i = 0, c1_idx = 0, c2_idx = 0;
while(i < goal.size()) {
if (c1_idx < cards1.size()) {
if (cards1[c1_idx].compare(goal[i]) == 0) {
i += 1;
c1_idx += 1;
continue;
}
}
if (c2_idx < cards2.size()) {
if (cards2[c2_idx].compare(goal[i]) == 0) {
i += 1;
c2_idx += 1;
continue;
}
}
break;
}
if (i == goal.size()) answer = "Yes";
return answer;
}
'.'