프로그래머스 카드뭉치 자바

1. 문제

---

* 문제설명

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

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

예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes"를, 만들 수 없다면 "No"를 return하는 solution 함수를 완성해주세요.

 

* 제한사항

• 1 ≤ cards1의 길이, cards2의 길이 ≤ 10
  • 1 ≤ cards1[i]의 길이, cards2[i]의 길이 ≤ 10
  • cards1과 cards2에는 서로 다른 단어만 존재합니다.
• 2 ≤ goal의 길이 ≤ cards1의 길이 + cards2의 길이
  • 1 ≤ goal[i]의 길이 ≤ 10
  • goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있습니다.
• cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.

* 입출력예

cards1                                           cards2                          goal                                                                              result

["i", "drink", "water"]	["want", "to"]	["i", "want", "to", "drink", "water"]	"Yes"
["i", "water", "drink"]	["want", "to"]	["i", "want", "to", "drink", "water"]	"No"

 

2. 접근 방식

---

처음 문제를 읽고 dfs를 활용하려고 했으나 배열을 순차적으로 순회해야하는 문제의 조건때문에 투포인터를 활용하기로 했다.

 

투포인터를 활용해 card1과 card2에서 goal과 같은 값을 발견하면 cnt를 증가시키고 cnt의 값이 goal의 length와 같으면 "Yes"를 출력하게 된다.

다만 주의 할 점은 idx1,idx2의 값이 배열의 인덱스를 넘는 경우를 고려해야한다는 것이다. 

 

3. 구현

---

class Solution {  
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "No";
        int idx1 = 0;
        int idx2 = 0;
        int cnt = 0;
        for (int i=0; i<goal.length; i++) {
            if (goal[i].equals(cards1[idx1])) {
                if (idx1 + 1 < cards1.length) {
                    idx1++;    
                } 
                cnt++;
                continue;
            } 
            if (goal[i].equals(cards2[idx2])) {
                if (idx2 + 1 < cards2.length) {
                    idx2++;    
                }        
                cnt++;
            }        
        }    
        if (cnt == goal.length) {
            answer = "Yes";
            return answer;
        } 
        return answer;
    }
}

 

4. 정리

---

아쉬웠던 점은 반복문을 돌릴 때 조건문을 하나 추가해 "No"를 출력하는 상황을 만들지 못한 것이다. 해당 문제의 경우 배열의 길이 자체가 작은 수 이기에 시간복잡도가 높이 않았다. 하지만 범위가 훨씬 컸을 경우 시간 복잡도를 고려해 card1, card2 둘다 일치하지 않으면 "No"를 return하도록 해야한다.