[프로그래머스] 카드 뭉치 Lv1 JAVA [투포인터][큐][엄탱]

문제 링크

프로그래머스

문제 설명

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

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

예를 들어 첫 번째 카드 뭉치에 순서대로 ["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 함수를 완성해 주세요.

제한사항

cards1과 cards2에는 서로 다른 단어만 존재합니다.

해설 1

해당 문제는 두 가지 정도 중요한 포인트가 있다고 생각한다.

 

1. 카드 뭉치에서 카드를 뽑을 때는 순서대로 뽑는 게 중요하다.

2. 제한사항에서 cards1과 cards2에는 서로 다른 단어만 존재한다.

 

1번을 보고 Queue를 이용하면 좋겠다고 생각했고, 2번을 보고 Queue를 사용해도 괜찮다고 생각했다.

2번 같은 제한사항이 없으면 위와 같은 방법으로 하면 안 되고 DFS를 병행해야 풀 수 있을 거라고 판단했다.

 

접근 방식은 기존 두 개의 카드 뭉치를 두개의 Queue에 넣어주고 만들어야 하는 카드 뭉치 배열을 순환하면서 각각 Queue에서 해당하는 단어가 있는지 탐색해 나가면 된다.

 

여기까지가 내가 생각했던 방식이다.

하지만, 다른 사람이 짠 코드를 보고 좀 더 쉽게 접근할 수 있다고 판단했다.

해설 2

간단하게 설명하자면 나는 큐를 이용해서 두 개의 카드 뭉치에서 앞에 단어만 가져왔지만, 좀 더 쉽게 생각해서 각 배열마다 포인트를 만들어줘서 단어를 사용하면 포인트를 하나씩 오른쪽으로 이동해 주면 된다.

코드 1

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "Yes";
        
        Queue<String> q1 = initQueue(cards1);
        Queue<String> q2 = initQueue(cards2);
        
        for (String g: goal) {
            if (!q1.isEmpty() && g.equals(q1.peek())) {
                q1.poll();
            } else if (!q2.isEmpty() && g.equals(q2.peek())) {
                q2.poll();
            } else {
                return "No";
            }
        }
        
        return answer;
    }
    
    private Queue<String> initQueue(String[] ss) {
        Queue<String> q = new LinkedList<>();
        for (String s: ss) {
            q.offer(s);
        }
        return q;
    }
}

코드 2 (다른 사람 풀이)

import java.io.*;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        int cardIdx1 = 0;
        int cardIdx2 = 0;

        for(int i=0; i<goal.length; i++){
            String target = goal[i];

            if(cardIdx1 < cards1.length && target.equals(cards1[cardIdx1]))
                cardIdx1 ++;
            else if (cardIdx2 < cards2.length && target.equals(cards2[cardIdx2]))
                cardIdx2++;
            else
                return "No";
        }


        return "Yes";
    }
}