[프로그래머스] 카드 뭉치 (Lv.1)

---

문제 링크

---

프로그래머스 - 카드 뭉치

문제 설명

---

두 카드 묶음 cards1, cards2와 목표 배열 goal이 주어진다. 각 카드 묶음은 앞에서부터 순서대로만 사용할 수 있다. goal 순서대로 카드를 모두 사용할 수 있으면 "Yes", 없으면 "No"를 반환하라.

예) cards1=["i","drink","water"], cards2=["want","to"], goal=["i","want","to","drink","water"] → "Yes"

내 풀이

---

cards1, cards2에 각각 별도 인덱스 idx1, idx2를 관리한다. goal을 순서대로 순회하며 cards1 또는 cards2의 현재 앞 카드와 매치되면 해당 인덱스를 전진시킨다. 둘 다 매치되지 않으면 즉시 "No"를 반환하고, 모두 순회하면 "Yes"를 반환한다.

#include <string>
#include <vector>

using namespace std;

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
    int idx1 = 0;
    int idx2 = 0;
    
    for(string temp : goal)
    {
        if(idx1 < cards1.size() && cards1[idx1] == temp) 
            idx1++;
        else if(idx2 < cards2.size() && cards2[idx2] == temp) 
            idx2++;
        else
            return "No";
    }
    
    return "Yes";
}

시간복잡도 분석

---

goal을 한 번 순회하므로 O(n) (n = goal의 길이).

goal의 길이 ≤ 100이므로 충분히 통과 가능하다.

오답노트

---

처음에 cards1, cards2, goal을 같은 인덱스 idx로 접근했다. 각 카드 묶음은 독립적으로 앞에서부터 사용해야 하므로 별도 인덱스가 필요하다.

후기

---

queue<string> q1, q2;
for (string s : cards1) q1.push(s);      
for (string s : cards2) q2.push(s);

for (string g : goal) 
{
      if (!q1.empty() && q1.front() == g) q1.pop();
      else if (!q2.empty() && q2.front() == g) q2.pop();
      else return "No";
}

return "Yes";

이런 식으로 큐로도 풀 수 있었다. 풀다가 긴가민가해서 포기했었는데.

• algorithm
• codingtest
• queue