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

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

프로그래머스

문제

주어진 카드뭉치 cards1과 cards2를 활용하여 goal의 문장을 완성할 수 있는지 판단하라.

각 카드뭉치는 순서대로만 꺼낼 수 있으며, 한번 사용한 카드는 재사용 할 수 없다.

 

최초접근

Map을 사용해 cards1과 cards2 정보를 모두 담은 후 goal을 순회하여 순서대로 꺼낼 수 있는지 체크하는 로직을 작성

 

public static String solution(String[] cards1, String[] cards2, String[] goal) {
        boolean isAble = false;

        Map<String, String> m = new HashMap<>();
        for(int i = 0; i < cards1.length; i++){
            m.put(cards1[i], "cards1:" + i);
        }
        for(int i = 0; i < cards2.length; i++){
            m.put(cards2[i], "cards2:" + i);
        }

        String lastArr = "";
        int lastIdx = 0;
        for(String g : goal){
            if(m.containsKey(g)){
                String[] v = m.get(g).split(":");
                int idx = Integer.parseInt(v[1]);
                if("".equals(lastArr)){
                    lastArr = v[0];
                    lastIdx = idx;
                    isAble = true;
                } else {
                    if(lastArr.equals(v[0])){
                        if(lastIdx <= idx){
                            isAble = true;
                        } else {
                            isAble = false;
                        }
                        lastIdx = idx;
                    } else {
                        lastIdx = 0;
                        lastArr = v[0];
                        if(lastIdx <= idx){
                            isAble = true;
                        } else {
                            isAble = false;
                        }
                        lastIdx = idx;
                    }
                }
            }
        }

        return isAble ? "Yes" : "No";
    }

 

수정

예외가 발생하였다. gpt가 진단한 해당 코드의 문제점 :

1.단어 순서가 유지되지 않음 goal을 순서대로 처리하면서, cards1과 cards2에서 올바른 순서로 나오는지 체크해야 하는데, 현재 방식은 Map을 사용해 단순히 단어 위치만 저장하기 때문에 순서를 보장하지 못함.

2.lastIdx 초기화 문제 lastIdx = 0; 로 설정되어 있지만, goal의 첫 단어가 cards1이나 cards2에서 0번 인덱스에 존재하지 않으면 잘못된 비교가 발생할 수 있음.

3.불필요한 Map 사용 goal을 순서대로 탐색하면서 cards1과 cards2에서 올바른 위치에 있는지 확인하면 되므로, Map이 필요 없음.

 

해당 문제를 해결하기 위해

카드의 순서를 보장해야 한다. Map은 순서를 보장하지 않으므로 이 문제를 해결하기 위한 방법으로 적절하지 않다.

이 문제를 해결하기 위한 방법은 두가지가 있다고 진단받음.

1. FIFO방식의 Queue를 활용한다.
2. 각 배열을 순서대로 순회하여 순서에 부합하는지 체크한다.

 

수정코드 1. Queue활용

public static 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 g : goal){
            if(!queue1.isEmpty() && queue1.peek().equals(g)){ //queue에 g가 존재하는지 체크
                queue1.poll(); //맨 앞의 단어를 꺼냄
            } else if(!queue2.isEmpty() && queue2.peek().equals(g)){
                queue2.poll(); //맨 앞의 단어를 꺼냄
            } else {
                return "No";
            }
        }

        return "Yes";
    }

 

수정코드 2. 배열을 사용한 방법

public String solution(String[] cards1, String[] cards2, String[] goal) {
    int idx1 = 0, idx2 = 0;  // cards1과 cards2의 현재 탐색 위치
    
    for (String g : goal) {
        // cards1에서 현재 단어 찾기
        if (idx1 < cards1.length && cards1[idx1].equals(g)) {
            idx1++;
        }
        // cards2에서 현재 단어 찾기
        else if (idx2 < cards2.length && cards2[idx2].equals(g)) {
            idx2++;
        }
        // 둘 다 해당하지 않으면 실패
        else {
            return "No";
        }
    }
    
    return "Yes"; // 모든 단어를 순서대로 찾을 수 있다면 "Yes" 반환
}

 

새로 알게된 점

1. 순서 보장이 필요한 경우, 특히 선입선출이 필요한 경우에 Queue를 활용하면 간단하게 처리가 가능하다.

    - queque.peek() : 맨 앞 원소 확인

    - queque.poll() : 맨 앞 원소를 queue로부터 꺼냄

2. 배열 안에서 다른 배열들을 순회해야 하는 경우, 각 배열 별로 인덱스 변수를 활용하여 처리할 수 있다.