[프로그래머스/Day 12] 카드 뭉치 - pop_back 방식의 함정과 해결책

오늘은 프로그래머스 '카드 뭉치' 문제를 풀면서 겪었던 시행착오와 해결 과정을 공유하려고 합니다. 효율성을 위해 pop_back을 활용한 역방향 탐색을 시도했으나, 특정 테스트 케이스에서 실패했던 원인을 분석하고 올바른 접근법을 정리해 보았습니다.

1. 문제 개요

이 문제는 두 개의 문자열 배열 cards1, cards2가 주어졌을 때, 이 카드들을 순서대로 사용하여 목표 배열 goal을 만들 수 있는지 판별하는 문제입니다.

• 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 꺼낼 수 있습니다.
• 한 번 사용한 카드는 다시 사용할 수 없습니다.
• 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
• 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

---

2. 첫 번째 접근: (시행착오)

처음에는 vector의 특성을 고려하여 효율적인 접근을 시도했습니다. vector의 앞부분 요소를 제거(erase)하면 O(N)의 시간이 걸리지만, 뒷부분을 제거(pop_back)하면 O(1)의 시간이 걸립니다.

그래서 "goal과 카드 뭉치를 뒤에서부터 비교하며 깎아나가면 효율적이지 않을까?" 라고 생각하여 아래와 같이 코드를 작성했습니다.

// 매개변수의 자료형을 vector를 사용하고 있으므로, pop_back을 최대한 활용하는 방향으로 고려
// 1. goal의 길이만큼 다음을 반복한다.
// 2. cards1/cards2의 마지막 단어와 goal의 마지막 단어를 비교한다.
// - 같다면, cards1/cards2와 goal에서 pop_back()
// - 둘 다 같지 않다면, 더이상 진행 불가로 No 반환
// 3. 모두 다 통과했다면 Yes 반환
#include <string>
#include <vector>

using namespace std;

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
    const size_t GOAL_SIZE = goal.size();
    
    // 1. goal의 길이만큼 다음을 반복한다.
    for(size_t t = 0; t < GOAL_SIZE; ++t)
    {
        string current_goal = goal.back();
        
        // 2. cards1/cards2의 마지막 단어와 goal의 마지막 단어를 비교한다.
        // - 같다면, cards1/cards2와 goal에서 pop_back()
        if(!cards1.empty() && cards1.back() == current_goal)
        {
            cards1.pop_back();
            goal.pop_back();
        } else if(!cards2.empty() && cards2.back() == current_goal)
        {
            cards2.pop_back();
            goal.pop_back();
        } else // - 둘 다 같지 않다면, 더이상 진행 불가로 No 반환
        {
            return "No";
        }
    }
    
    // 3. 모두 다 통과했다면 Yes 반환
    return "Yes";
}

 

문제점 및 실패 원인 (테스트 20, 21, 24 실패)

논리적으로 완벽해 보였지만, 채점 결과 3개의 테스트 케이스를 통과하지 못했습니다. 원인은 "사용하지 않고 남는 카드"에 있었습니다.

문제 조건상 cards1이나 cards2의 모든 카드를 다 써야 한다는 규칙은 없습니다. 만약 뒤쪽에 쓰지 않는 카드(더미 데이터)가 남아 있다면, 제 코드는 그 카드가 길을 막고 있다고 판단하여 실패 처리를 하게 됩니다.

[반례 예시]

• cards1: ["A", "B", "C"] (여기서 "C"는 쓰지 않음)
• cards2: ["D", "E"]
• goal: ["A", "B", "D", "E"]

위 경우 정답은 Yes여야 합니다. 하지만 제 로직(역방향 비교)에서는 goal의 마지막인 "E"와 cards1의 마지막인 "C"를 비교하게 되고, 당연히 다르기 때문에 cards1에 정답인 "A", "B"가 앞에 있음에도 불구하고 접근조차 못 하고 No를 반환하게 됩니다.

 

---

3. 두 번째 접근: 로직의 변경 (Index 활용)

뒤에서부터 비교하는 방식은 "남는 카드" 때문에 사용할 수 없다는 것을 깨닫고, 정석대로 앞에서부터 비교하는 방식으로 변경했습니다.

이때 vector의 앞부분을 erase하면 성능 저하가 발생할 수 있으므로, 원본 데이터를 건드리지 않고 현재 가리키고 있는 위치(Index)만 저장하는 변수를 사용했습니다.

 

// 1. goal의 단어를 순서대로 하나씩 확인한다.
// 2. cards1에서 가져올 수 있는지 확인하고 있으면 다음 카드로 넘어간다.
// 3. cards2에서 가져올 수 있는지 확인하고 있으면 다음 카드로 넘어간다.
// 4. 둘 다 카드가 없으면 매치가 안되므로 No를 반환한다.
// 5. 1~4를 통과했으면 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;
    
    // 1. goal의 단어를 순서대로 하나씩 확인한다.
    for(const string& target : goal)
    {
        // 2. cards1에서 가져올 수 있는지 확인하고 있으면 다음 카드로 넘어간다.
        if(idx1 < cards1.size() && cards1[idx1] == target)
        {
            idx1++;
        }
        // 3. cards2에서 가져올 수 있는지 확인하고 있으면 다음 카드로 넘어간다.
        else if(idx2 < cards2.size() && cards2[idx2] == target)
        {
            idx2++;
        }
        // 4. 둘 다 카드가 없으면 매치가 안되므로 No를 반환한다.
        else
        {
            return "No";
        }
    }
    
    // 5. 1~4를 통과했으면 Yes를 반환한다.
    return "Yes";
}

이렇게 수정하면 남는 카드가 뒤에 있더라도 상관없이 앞에서부터 순서대로 매칭을 확인할 수 있어 모든 테스트 케이스를 통과하게 됩니다.

 

---

4. 정리

• 자료구조의 특징 활용: vector의 pop_back이 효율적인 것은 맞지만, 문제의 로직(순서 보장, 남는 데이터 허용 여부)과 맞지 않다면 사용할 수 없습니다.
• 반례 생각하기: "모든 데이터를 다 쓰는가?" 아니면 "일부만 쓰고 남는 데이터가 있는가?"를 고려하는 것이 중요합니다. 남는 데이터가 있을 때 역방향 탐색은 위험할 수 있습니다.
• 인덱스 포인터: 배열을 수정하지 않고 int형 변수로 인덱스만 관리하는 방식은 코딩 테스트에서 가장 안전하고 효율적인(O(N)) 방법 중 하나입니다.