< 프로그래머스 C++ > 카드 뭉치

문제 설명

영어 단어가 적힌 카드 뭉치 두 개로 원하는 단어 배열(goal)을 만들 수 있는지 판별하는 문제

• 카드 뭉치에서 카드를 순서대로 한 장씩 사용
• 한 번 쓴 카드는 다시 쓸 수 없음
• 카드를 건너뛰고 다음 카드로 넘어갈 수 없음
• 카드 뭉치의 단어 순서는 바꿀 수 없음

만들 수 있으면 "Yes", 못 만들면 "No" 반환

예시

cards1 = ["i", "drink", "water"]
cards2 = ["want", "to"]
goal   = ["i", "want", "to", "drink", "water"]

cards1에서 "i" 

cards2에서 "want", "to" 

cards1에서 "drink", "water" 순서로 사용
>> "Yes"

---

문제 해석

처음엔 find로 카드가 있는지만 확인하면 된다고 생각했다

문제를 다시 보면 순서대로 한 장씩 이라는 조건이 있다
cards1에서 "water"를 쓰고 싶어도 앞에 있는 "i", "drink"를 먼저 다 써야 꺼낼 수 있다는 뜻

그러니까 단순히 카드가 있냐 없냐가 아니라 지금 맨 앞 카드가 goal과 맞는지 봐야 한다
각 카드 뭉치마다 "지금 어디까지 썼는지" 인덱스로 추적하면 깔끔하게 풀린다

---

문제 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
    int idx1 = 0, idx2 = 0;

    for(int i = 0; i < goal.size(); ++i)
    {
        if(idx1 < cards1.size() && cards1[idx1] == goal[i])
            idx1++;
        else if(idx2 < cards2.size() && cards2[idx2] == goal[i])
            idx2++;
        else
            return "No";
    }

    return "Yes";
}

---

핵심 포인트

1. 인덱스로 "지금 맨 앞 카드" 추적하기

각 카드 뭉치는 순서대로만 꺼낼 수 있으니까, 지금 꺼낼 카드 위치를 인덱스로 들고 있으면 된다

int idx1 = 0, idx2 = 0;

idx1은 cards1에서 다음에 꺼낼 카드, idx2는 cards2에서 다음에 꺼낼 카드
goal을 하나씩 처리하면서 매칭된 쪽의 인덱스만 1씩 늘려주면 된다

2. 비교는 맨 앞만

cards1[idx1] == goal[i]

cards1 전체를 뒤지는 게 아니라 맨 앞 카드 하나하고만 비교한다
이렇게 해야 "순서대로 사용"이라는 조건을 자연스럽게 만족시킬 수 있다

3. 범위 체크

if(idx1 < cards1.size() && cards1[idx1] == goal[i])

처음엔 그냥 cards1[idx1] == goal[i]만 써볼까 했는데, 인덱스가 cards1 크기를 넘어가면 런타임 에러가 난다

C++의 &&는 앞 조건이 false면 뒤는 아예 평가 안 하는 단축 평가 방식이라
이 순서로 쓰면 인덱스가 범위를 벗어나도 cards1[idx1]에 접근하지 않는다

---

트러블슈팅

원인

처음에 find를 통해서 결과 카드에 들어가있는 카드면 true를 반환하면 된다고 생각해서 이렇게 작성했다.

for(int i = 0; i < goal.size(); ++i)
{
    if(find(cards1.begin(), cards1.end(), goal[i]) != cards1.end())
        continue;
    else if(find(cards2.begin(), cards2.end(), goal[i]) != cards2.end())
        continue;
    else
        return "No";
}
return "Yes";

언뜻 보면 맞는 것 같지만 테스트케이스 절반 정도가 실패했다

문제 파악

문제 조건을 다시 읽어보니 이런 문구가 있었다

원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다

 

find는 그냥 "어딘가에 있는지"만 봐주는 함수다
순서를 전혀 신경쓰지 않으니까, 실제로는 못 꺼내는 카드인데도 통과시켜버린다

cards1	["i", "drink", "water"]
cards2	["want", "to"]
goal	["water", "i", ...]

이 경우 goal[0] = "water"인데 cards1에는 분명 "water"가 있다
그래서 find는 통과시킨다

근데 실제로는 cards1은 "i" → "drink" → "water" 순서로만 꺼낼 수 있다
처음부터 "water"를 꺼내는 건 불가능

내 코드는 카드가 있다 = 사용 가능하다 라고 잘못 판단하고 있던 거였다

해결 방법

각 카드 뭉치마다 지금 어디까지 썼는지 인덱스로 추적하는 방식으로 바꿨다

int idx1 = 0, idx2 = 0;

if(idx1 < cards1.size() && cards1[idx1] == goal[i])
    idx1++;

cards1[idx1]은 "지금 cards1에서 꺼낼 수 있는 맨 앞 카드" 다

이거랑 goal[i]를 비교하면 자연스럽게 "순서대로 사용" 조건이 지켜진다

 

순서가 중요한 문제에서는 인덱스를 이용하는 것이 좋다는 것을 알았다.

---

 

코드 흐름

예시를 직접 따라가보면 어떻게 동작하는지 한눈에 보인다

cards1 = ["i", "drink", "water"]
cards2 = ["want", "to"]
goal   = ["i", "want", "to", "drink", "water"]

i goal[i]

cards1[idx1]

cards2[idx2]

결과 idx1 idx2

0	"i"	"i"	-	cards1 사용	1	0
1	"want"	"drink"	"want"	cards2 사용	1	1
2	"to"	"drink"	"to"	cards2 사용	1	2
3	"drink"	"drink"	(끝)	cards1 사용	2	2
4	"water"	"water"	(끝)	cards1 사용	3	2

goal을 끝까지 다 매칭 >> "Yes"