[Java] 코딩 45 - 프로그래머스 기출 문제(JAVA) / 카드 뭉치 / Day 37

🃏 카드 뭉치

📘 문제 설명

코니는 영어 단어가 적힌 카드 뭉치 두 개를 사용하여 원하는 순서의 단어 배열을 만들 수 있는지 확인하려 합니다. 단어를 하나씩 사용할 때, 각 카드 뭉치에서 반드시 순서대로 카드를 꺼내야 하며, 카드를 건너뛰거나 순서를 바꿀 수 없습니다. 주어진 goal 배열을 완성할 수 있으면 "Yes", 없으면 "No"를 반환하는 프로그램을 작성해야 합니다.

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

프로그래머스

 

📌 제한조건

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

💡 개념 설명

• 알고리즘 핵심: 두 개의 포인터를 사용하여 각 카드 뭉치에서 다음에 사용할 수 있는 카드의 위치를 추적하는 그리디(Greedy) 접근 방식입니다. goal 배열의 각 단어를 확인할 때마다 현재 두 카드 뭉치의 맨 위에 있는 카드와 비교합니다.
• 로직 단계:
  1. 각 카드 뭉치를 가리킬 인덱스 변수 idx1과 idx2를 0으로 초기화합니다.
  2. goal 배열을 처음부터 끝까지 순회합니다.
  3. 현재 단어(goal[i])가 cards1[idx1]과 일치하는지 확인합니다. (배열 범위를 넘지 않는지 먼저 체크)
  4. 일치한다면 idx1을 1 증가시키고 다음 단어로 넘어갑니다.
  5. 일치하지 않는다면 cards2[idx2]와 비교하여 일치할 경우 idx2를 1 증가시킵니다.
  6. 두 카드 뭉치의 현재 카드와 모두 일치하지 않는다면 순서를 맞출 수 없는 상태이므로 즉시 "No"를 반환합니다.
  7. 모든 단어를 성공적으로 순회했다면 "Yes"를 반환합니다.

📎 입출력 예시

💻 프로그래머스 제출용 코드

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        int idx1 = 0; // cards1을 추적할 포인터
        int idx2 = 0; // cards2를 추적할 포인터

        for (String target : goal) {
            // cards1의 현재 카드와 일치하는지 확인
            if (idx1 < cards1.length && target.equals(cards1[idx1])) {
                idx1++;
            } 
            // cards2의 현재 카드와 일치하는지 확인
            else if (idx2 < cards2.length && target.equals(cards2[idx2])) {
                idx2++;
            } 
            // 어느 쪽과도 일치하지 않으면 실패
            else {
                return "No";
            }
        }

        return "Yes";
    }
}

🖥️ IntelliJ 실행용 코드

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

        for (String target : goal) {
            if (idx1 < cards1.length && target.equals(cards1[idx1])) {
                idx1++;
            } else if (idx2 < cards2.length && target.equals(cards2[idx2])) {
                idx2++;
            } else {
                return "No";
            }
        }
        return "Yes";
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // 테스트 케이스 1
        String[] cards1_1 = {"i", "drink", "water"};
        String[] cards2_1 = {"want", "to"};
        String[] goal_1 = {"i", "want", "to", "drink", "water"};
        System.out.println("결과 1: " + sol.solution(cards1_1, cards2_1, goal_1)); // "Yes"

        // 테스트 케이스 2
        String[] cards1_2 = {"i", "water", "drink"};
        String[] cards2_2 = {"want", "to"};
        String[] goal_2 = {"i", "want", "to", "drink", "water"};
        System.out.println("결과 2: " + sol.solution(cards1_2, cards2_2, goal_2)); // "No"
    }
}

📎 결과