[프로그래머스/JAVA] 카드 뭉치

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 💡 아이디어
• 👩🏻‍💻 최종 코드
• 🕑 시간 복잡도

 

 

 

🔗 문제 바로가기

 

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

프로그래머스

 

---

📌 문제 요약

 

 

📄 문제 상황

코니는 영어 단어가 적힌 카드 뭉치 2개를 선물 받았다.

우리는 이 카드 뭉치들에 있는 카드들을 사용해서 원하는 순서의 문장을 만들 수 있는지 확인해야 한다.

 

 

📢 카드 사용 규칙

• 원하는 카드 뭉치에서 맨 앞의 카드부터 순서대로 한 장씩 사용해야 한다. (건너뛰기 불가)
• 한 번 사용한 카드는 다시 사용할 수 없다.
• 카드 뭉치에 있는 단어의 순서는 바꿀 수 없다.

 

🎯 목표

• cards1과 cards2에 있는 단어들을 이용해서
  주어진 goal 배열을 정확히 만들 수 있는지 판별해야 한다.
• 만들 수 있으면 "Yes", 만들 수 없으면 "No"를 반환한다.

 

 

🔎 예시

cards1 = ["i", "drink", "water"]
cards2 = ["want", "to"]
goal   = ["i", "want", "to", "drink", "water"]

• "i"  👉🏻 cards1에서 꺼내기
• "want" 👉🏻 cards2에서 꺼내기
• "to" 👉🏻 cards2에서 꺼내기
• "drink" 👉🏻 cards1에서 꺼내기
• "water" 👉🏻 cards1에서 꺼내기

즉, goal 배열을 정확히 만들 수 있으므로 "Yes"를 반환하면 된다.

 

 

cards1 = ["i", "water", "drink"]
cards2 = ["want", "to"]
goal   = ["i", "want", "to", "drink", "water"]

• "i" 👉🏻 cards1에서 꺼내기
• "want" 👉🏻 cards2에서 꺼내기
• "to" 👉🏻 cards2에서 꺼내기
• "drink" 👉🏻 cards1에서 꺼내려고 했으나, "drink" 앞에 있는 "water"를 아직 사용하지 않았으므로 "drink"를 꺼낼 수 없음

즉, goal 배열을 완성할 수 없으므로 "No"를 반환하면 된다.

 

---

💡 아이디어

1️⃣ 포인터 두 개로 맨 앞만 가리키기

• i 👉🏻 cards1의 현재 맨 앞 인덱스를 가리키도록 한다.
• j 👉🏻 cards2의 현재 맨 앞 인덱스를 가리키도록 한다.

int i = 0;
int j = 0;

 

 

2️⃣ 각 단어 g에 대해서 그리디하게 선택하기

• cards1[i] == g이면 👉🏻 i++ 해주기 (cards1에서 한 장 사용했다는 의미)
• cards2[j] == g이면 👉🏻 j++ 해주기 (cards2에서 한 장 사용했다는 의미)
• 둘 다 아니면 👉🏻 규칙을 더이상 만들 수 없다는 의미이므로 "No" 반환하기

for(String g : goal){
    if(i < cards1.length && cards1[i].equals(g)){
        i++;
    }
    else if(j < cards2.length && cards2[j].equals(g)){
        j++;
    }
    else{
        return "No";
    }
}

 

위와 같이 그리디하게 선택하는 이유는,

goal은 순서가 고정이고, 각 카드 뭉치에서는 앞에서 부터 차례대로만 카드를 뽑을 수 있으므로

현재 필요한 단어를 지금 당장 뽑는 선택 외에는 더 나은 대안이 없다.

 

---

👩🏻‍💻 최종 코드

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        
        int i = 0;
        int j = 0;
        
        for(String g : goal){
            if(i < cards1.length && cards1[i].equals(g)){
                i++;
            }
            else if(j < cards2.length && cards2[j].equals(g)){
                j++;
            }
            else{
                return "No";
            }
        }
        
        return "Yes";
    }
}

 

---

🕑 시간 복잡도

1️⃣ goal 순회

for(String g : goal) {
    ....
}

 

goal 배열의 길이를 N이라고 할 때,

이 루프는 최대 N번 반복하므로 시간 복잡도는 O(N)이다.

 

이것 이외의 연산들은 모두 단순 비교 및 대입이므로 O(1)의 시간 복잡도를 갖는다.

 

 

👉🏻 따라서 최종 시간 복잡도는 O(N)이다.

       (이때 N은 goal 배열의 길이이다.)