프로그래머스 연습 - 카드 뭉치 [C++]

 

 

 티스토리 만들고 나름 컴공과라고...^^ 개발 일지를 쓰려고 백준을 켰습니다. 그렇게 대충 쉬운 문제 풀어 올려야지^^ 했다가 다 틀리고 멘탈이 털린 채 그만뒀었죠. 나름 실버 2인데 브론즈 2짜리 문제를? 틀린다? 제가 백준 실버의 수치입니다... 

 여튼 그렇게 짱나서 문제 안 풀어! 했다가 심심해서 푼 문제가 잘 맞았네요. 다행입니다. 백준 실버의 가오를 쪼끔이나마 챙겼습니다. 쉬운 문제인 거 맞지만 여하튼 맞은 건 맞은 겁니다.

 

카드뭉치

https://school.programmers.co.kr/learn/courses/30/lessons/159994

프로그래머스

 

 

1. 문제 요약

 

 문제를 간략히 요약해보자면, 두 카드 뭉치(cards1, cards2)가 쌓여있는데 가장 앞에 있는 단어만을 사용할 수 있다고 가정했을 때 주어진 문장(goal)을 만들 수 있을까?입니다. 예를 들자면

 

cards1의 단어들 -> "b" "c" 

cards2의 단어들 -> "a" "k"

goal의 단어들 -> "b" "a" "c" "k"

 

일 때, goal의 단어로 만들 수 있을까? 입니다. 문제는 가장 앞에(왼쪽) 있는 단어만 사용할 수 있다는 거죠. 이 예시 같은 경우 

 

(cards1는 c1, cards2는 c2)

 c1 -> c2 -> c1 -> c2

 

순서로 하면 됩니다. 그런데 goal의 단어들이 "b" "k" "a" "c" 라면 곧바로 c2의 c 전에 k를 사용할 수 없으니 불가능합니다. 그러면 어떻게 풀 수 있을까요?

 

 

2. 풀이 방법

 

 알고리즘을 간단히 설명해보자면 goal의 가장 앞에 있는 단어가 c1이나 c2에 있으면 그다음 단어로 넘어가는 형식을 선택했습니다. 다음 단어로 넘어가게 하는 방식은 인덱스 +1을 하거나, 아님 그 단어를 제거하는 방식이 있겠죠.

 

<인덱스 +1>

 

#include <string>
#include <vector>

using namespace std;

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
    // 일단 가능하다고 가정함
    string answer = "Yes";
    
    // 현재 구하는 or 현재 가장 앞에 있는 단어의 인덱스
    // c1 = cards1, c2 = cards2, g = goal
    int c1 = 0, c2 = 0, g = 0;
    
    while(1){
        // g가 goal의 끝까지 갔다면 남은 단어가 없으므로 빠져나옴
        if(g == goal.size()){
            break;
        }
        
        // 아직 끝이 아니라면
        else{
            // goal의 단어가 cards1에 있다면
            if(goal[g] == cards1[c1]){
                // g와 c1을 하나 늘림
                g++;
                c1++;
            }
            
            // cards1에 없고 cards2에 있다면
            else if(goal[g] == cards2[c2]){
                // g와 c2을 하나 늘림
                g++;
                c2++;
            }
            
            // 둘 다 없다면 만들 수 없음
            else{
                answer = "No";
                break;
            }
        }
    }
    
    return answer;
}

 

 

근데 이거 큐 방식으로도 풀 수 있지 않을까요? 가장 먼저 들어온 걸 제외한다는 방식으로 한다면 큐로 할 수 있을 것 같습니다. 언젠가 기력이 있다면 해보는 걸로... ^^b