[프로그래머스] 카드 뭉치 - 159994 (Java)

문제 URL

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

문제 설명

두 개의 카드 더미(cards1, cards2)와 목표 문자열 배열(goal)이 주어졌을 때, goal 배열의 각 문자열을 cards1과 cards2의 순서를 유지하면서 만들 수 있는지 판별하는 문제입니다. 각 카드 더미는 순서가 고정되어 있으며, goal 배열의 문자열 순서도 유지해야 합니다.

---

나의 풀이

1. 기본 풀이: 인덱스 활용

• 각 카드 더미의 현재 위치를 나타내는 인덱스(idx1, idx2)를 활용해 순서대로 문자열을 비교합니다.
• goal의 각 문자열이 cards1이나 cards2의 현재 위치 문자열과 일치하면 해당 인덱스를 증가시킵니다.
• 문자열이 일치하지 않으면 "No"를 반환하며 루프를 종료합니다.

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "Yes"; // 기본 값 "Yes"로 설정
        int idx1 = 0; // cards1의 현재 위치를 나타내는 인덱스
        int idx2 = 0; // cards2의 현재 위치를 나타내는 인덱스
        
        // goal 배열의 각 문자열을 순회
        for (String str : goal) {
            if (idx1 < cards1.length && cards1[idx1].equals(str)) { 
                idx1++; // cards1에서 일치하면 idx1 증가
            } else if (idx2 < cards2.length && cards2[idx2].equals(str)) {
                idx2++; // cards2에서 일치하면 idx2 증가
            } else {
                answer = "No"; // 두 카드 더미 모두에서 일치하지 않으면 "No"
                break;
            }
        }

        return answer;
    }
}

2. 큐 활용 풀이: ArrayDeque를 활용해 각 카드 더미를 큐로 변환

• 각 카드 더미와 goal 배열을 ArrayDeque로 변환하여 큐처럼 사용합니다.
• goal의 각 문자열이 cardsDeque1이나 cardsDeque2의 앞(front) 문자열과 일치하면 해당 큐에서 값을 제거합니다.
• 일치하지 않는 경우 루프를 종료하고 "No"를 반환합니다.

import java.util.ArrayDeque;
import java.util.Arrays;

public class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        // 카드 더미와 goal 배열을 큐로 변환
        ArrayDeque<String> cardsDeque1 = new ArrayDeque<>(Arrays.asList(cards1));
        ArrayDeque<String> cardsDeque2 = new ArrayDeque<>(Arrays.asList(cards2));
        ArrayDeque<String> goalDeque = new ArrayDeque<>(Arrays.asList(goal));

        // goalDeque에 문자열이 남아있으면 계속 반복
        while (!goalDeque.isEmpty()) {
            // cardsDeque1의 front와 일치하는 경우
            if (!cardsDeque1.isEmpty() && cardsDeque1.peekFirst().equals(goalDeque.peekFirst())) {
                cardsDeque1.pollFirst(); // cardsDeque1에서 제거
                goalDeque.pollFirst();  // goalDeque에서 제거
            }
            // cardsDeque2의 front와 일치하는 경우
            else if (!cardsDeque2.isEmpty() && cardsDeque2.peekFirst().equals(goalDeque.peekFirst())) {
                cardsDeque2.pollFirst(); // cardsDeque2에서 제거
                goalDeque.pollFirst();  // goalDeque에서 제거
            }
            // 일치하지 않는 경우
            else {
                break;
            }
        }

        // goalDeque가 비었으면 "Yes", 아니면 "No" 반환
        return goalDeque.isEmpty() ? "Yes" : "No";
    }
}

---

배운 점

• 문제를 풀며 인덱스를 활용한 배열 탐색과 큐의 활용 차이를 비교할 수 있었습니다.
• 큐를 활용하면 코드의 가독성이 높아지지만, 입력 크기에 따라 메모리 사용량에 주의해야 한다는 점을 깨달았습니다.