[연습문제] 카드 뭉치

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

프로그래머스

---

문제 설명
코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다.

코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

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

예를 들어 첫 번째 카드 뭉치에 순서대로 ["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"

---

입출력 예 설명
입출력 예 #1

• 본문과 같습니다.

입출력 예 #2

• cards1에서 "i"를 사용하고 cards2에서 "want"와 "to"를 사용하여 "i want to"까지는 만들 수 있지만 "water"가 "drink"보다 먼저 사용되어야 하기 때문에 해당 문장을 완성시킬 수 없습니다. 따라서 "No"를 반환합니다.

---

두 개의 카드 뭉치가 주어지고, 원하는 단어 배열이 주어졌을 때, 이 단어 배열을 순서에 맞게 생성할 수 있는지 구하는 문제입니다.

 

만들어야 할 단어 배열은 항상 카드 뭉치의 원소들로만 이뤄져있기 때문에, 카드 원소들의 순서만 생각하면 됩니다.

1번 예시를 잘 살펴보면, goal의 순서는 다음과 같이 [A1, B1, B2, A2, A3]로 나타낼 수 있습니다.

반대로 2번 예시에서는 [A1, B1, B2, A3, A2]로 나타내게 됩니다.

 

숫자들만 살펴본다면 [1, 1, 2, 2, 3]은 "YES"를, [1, 1, 2, 3, 2]는 "NO"라고 볼 수 있습니다.

그런데 여기서 조금 더 생각해볼 거리가 있습니다.

 

문제 상의 조건에서는

• 한 번 사용한 카드는 다시 사용할 수 없습니다.

이런 조건을 명시해주었는데, 사용할 수 있는 단어들은 각각의 카드 뭉치의 첫 번째 값만 가능합니다.

다시 말해 특정 카드 뭉치를 사용하려 했을 때, 해당 카드 뭉치의 첫 번째 값이 우리가 원하는 단어가 아니라면 무조건 만들 수 없게 됩니다.

이 조건들을 활용해서 정답 코드를 작성해보겠습니다.

 

1. 자바

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

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        Queue<String> queue1 = new LinkedList<>(Arrays.asList(cards1));
        Queue<String> queue2 = new LinkedList<>(Arrays.asList(cards2));
        
        for (String word : goal) {
            if (!queue1.isEmpty() && queue1.peek().equals(word)) {
                queue1.poll(); // cards1에서 제거
            } else if (!queue2.isEmpty() && queue2.peek().equals(word)) {
                queue2.poll(); // cards2에서 제거
            } else {
                return "No"; // 조건을 만족하지 못하면 "No" 반환
            }
        }
        return "Yes"; // 모든 단어를 순서대로 배치할 수 있으면 "Yes"
    }
}

 

2. 파이썬

def solution(cards1, cards2, goal):
    # 단어 배열에서 단어를 하나씩 가져옵니다.
    for word in goal:
        # 1번 뭉치가 남아 있고, 해당 뭉치의 첫 값이 word일 경우
        if cards1 and cards1[0] == word:
            # 해당 단어를 사용 처리합니다.
            cards1.remove(word)
        # 2번 뭉치가 남아 있고, 해당 뭉치의 첫 값이 word일 경우
        elif cards2 and cards2[0] == word:
            # 해당 단어를 사용 처리합니다.
            cards2.remove(word)
        # 두 경우가 모두 아니라면 문자열 생성이 불가능하므로
        else:
            return "No"
    # 모든 배열이 성공적으로 생성된다면
    return "Yes"

 

제가 고민했던 부분은 카드 뭉치의 순서를 어떻게 나누냐였었는데, 이 부분은 if - elif (else if) 구조로 처리가 가능합니다.

 

정상적인 경우, goal의 단어들은 전부 cards1, cards2로 되어 있기 때문에 둘 중 하나의 뭉치에는 해당하는 단어들이 포함되어 있습니다.

만약 1번 뭉치에서 단어가 있었다면, if 분기에 따라서 다음 반복으로 넘어가게 됩니다.

1번 뭉치에는 이제 해당하는 단어가 없기 때문에, if문을 넘기고 elif (else if)에 따라 2번 뭉치를 확인합니다.

2번 뭉치에서 단어가 있으면 사용 처리를 하고 다음으로 넘어가죠. 그러면 다시 1번부터 검사를 진행합니다.

 

이렇게 if - elif (else if) 구조를 사용한다면, 1번 - 2번 or 2번 - 1번이 반복되도록 처리할 수 있습니다.