[프로그래머스][재귀][JAVA] 카드 뭉치

문제 제목

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

프로그래머스

풀이 방법

처음엔 되게 간단하게 생각했다.
left, right 인덱스를 나누어 cards1과 goal의 문자열이 같으면 left++, cards2와 goal의 문자열이 같으면 right++ 해주면서 차례차례 탐색해주는 방식으로 진행했는데 코드를 제출해보니 몇몇 테스트 케이스에서 실패가 나왔다.

그 이유를 고민해보니 모든 경우를 탐색하지 않아서 그런 것 같았다.

cards1	i	want	coffee
cards2	want	to
goal	i	want	to	want	coffee

대충 이런 예제가 있다고 해보자.
내가 기존에 생각한 방법대로 풀면

1. 먼저 cards1을 탐색해 i를 찾아낸다.
2. 또 cards1을 탐색해 want를 찾아낸다.
3. 그 다음 cards1을 탐색했지만 coffee와 to가 일치하지 않으므로 cards2로 넘어가 탐색했는데 역시 want와 to가 일치하지 않으므로 No라는 결과가 나오게 된다.

근데 cards1 -> cards2 차례로 탐색하는 것이 아니라 cards1도 탐색하고 cards2도 탐색하는 방식으로 풀면

1. cards1을 탐색해 i를 찾아내고 cards2에서는 일치하지 않으므로 넘긴다.
2. cards1을 탐색해 want를 찾아내고 cards2에서도 want를 찾아낸다.
3. cards1을 먼저 탐색한 경우에서는 to를 찾아낼 수 없으므로 탐색을 종료한다
4. cards2를 탐색한 경우에서는 to를 찾아낸다.
5. 이후 want, coffee 모두 찾아내 Yes라는 결과가 나온다

말로 표현을 잘 못해서 해설이 중구난방 횡설수설이지만 중요한 건 모든 경우의 수를 탐색하는 것이 중요하다는 것이다.
그래서 나는 재귀 함수를 사용했다.

소스 코드

class Solution {
    String[] cards1_global;
    String[] cards2_global;
    String[] goal_global;

    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "No";

        cards1_global = cards1;
        cards2_global = cards2;
        goal_global = goal;

        int left = 0;
        int right = 0;
        int index = 0;

        if(CheckCards(left, right, index)) {
            answer = "Yes";
        }

        return answer;
    }

    public boolean CheckCards(int left, int right, int index) {
        if (index == goal_global.length) {
            return true;
        }

        if(left == cards1_global.length) {
            if(!cards2_global[right].equals(goal_global[index])) {
                return false;
            }
        }
        else if(right == cards2_global.length) {
            if(!cards1_global[left].equals(goal_global[index])) {
                return false;
            }
        }
        else {
            if(!cards2_global[right].equals(goal_global[index]) && !cards1_global[left].equals(goal_global[index])) {
                return false;
            }
        }

        if(left < cards1_global.length && right < cards2_global.length) {
            return (CheckCards(left + 1, right, index + 1) || CheckCards(left, right + 1, index + 1));
        }
        else if(left < cards1_global.length && right == cards2_global.length) {
            return CheckCards(left + 1, right, index + 1);
        }
        else if(left == cards1_global.length && right < cards2_global.length) {
            return CheckCards(left, right + 1, index + 1);
        }
        else {
            return false;
        }
    }
}