[내일배움캠프][TIL] 23.12.22 (금) - 카드 뭉치

1. 코드카타

 

오늘 푼 알고리즘 문제는 '카드 뭉치' 이다.

 

카드 뭉치

 

이번 문제는 cards1에 있는 단어와 cards2에 있는 단어를 조합하여 goal에 있는 문장을 완성시킬 수 있으면 Yes를, 없으면 No를 return시키면 되는 문제다.

 

이번 문제의 가장 큰 핵심은 바로 '카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.' 이다.

이 조건 때문에 겉보기에는 조합이 가능해보여도 안 되는 경우가 있어서 틀릴 가능성이 생기게 된다.

 

그리고 다음 예제같은 경우에는 cards2에서 한번에 다 털어서 그렇지 사실 cards1, cards2, cards1, cards2 이런 식으로 번갈아가면서 goal의 문장을 완성시켜도 된다. 딱히 그러지 말라는 조건이 있는 것도 아니기 때문에.

 

 

그러면 이제 이걸 어떻게 구현시킬까?

우선 cards1, cards2, goal을 리스트화 시킨다.

var cardsList1 = cards1.toMutableList()
var cardsList2 = cards2.toMutableList()
var goalList = goal.toMutableList()

 

다음은 cards와 goal의 단어를 각각 비교하고, goal을 완성하는 단계다.

여기서 이걸 어떻게 구현시킬 건지가 중요한데, 조건 중에서 '한 번 사용한 카드는 다시 사용할 수 없습니다.'가 있다. 이걸 바꿔말하면 '한 번 사용한 카드는 제거할 수 있다'고 볼 수 있다.

 

즉, 이를 이용해서 하나의 메커니즘을 만든다.

if (cardsList1.isNotEmpty() && cardsList1[0] == word) {
	cardsList1.removeAt(0)
	goalList.removeAt(0)
}

 

cards1이 비어있지 않고, cards1의 맨 앞 단어가 goal의 맨 앞 단어와 일치하면 cards1의 맨 앞 단어와 goal의 맨 앞 단어를 각각 제거한다.

 

이 때, 0으로 고정한 이유는 '순서대로 사용해야 한다'는 조건 때문이다.

 

이런 식으로 cards1을 털고, 만약 cards1에서 털 단어가 없으면, cards2로 넘어간다.

else if (cardsList2.isNotEmpty() && cardsList2[0] == word) {
	cardsList2.removeAt(0)
	goalList.removeAt(0)
}

 

만약 cards1, cards2 모두 goal의 단어를 털지 못 할 경우, No를 return한다.

 

또, goal이 비어 있으면 단어를 모두 완성시킨 셈이기 때문에 Yes를 return한다.

 

 

이를 종합하면 다음과 같은 코드가 나온다.

class Solution {
    fun solution(cards1: Array<String>, cards2: Array<String>, goal: Array<String>): String {
        var answer: String = ""
        
        var cardsList1 = cards1.toMutableList()
        var cardsList2 = cards2.toMutableList()
        var goalList = goal.toMutableList()
        
        for (word in goal) {
            if (cardsList1.isNotEmpty() && cardsList1[0] == word) {
                cardsList1.removeAt(0)
                goalList.removeAt(0)
            }
            else if (cardsList2.isNotEmpty() && cardsList2[0] == word) {
                cardsList2.removeAt(0)
                goalList.removeAt(0)
            }
            else {
            answer = "No"
            break
            }
        }
        
        if (goalList.isEmpty()) answer = "Yes"
        
        return answer
    }
}

 

for문을 통해서 goal에 있는 단어를 싹 훌는다.

cards1에 있으면 for문을 반복하고, 없으면 cards2에 간다.

cards2에 있으면 for문의 첫번째, 즉 cards1부터 훑는 작업을 반복하고, 없으면 곧바로 No를 return하고 반복문을 종료한다.