카드 뭉치 | 프로그래머스

📍 카드 뭉치

💡 문제

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

• 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
• 한 번 사용한 카드는 다시 사용할 수 없습니다.
• 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
• 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes"를, 만들 수 없다면 "No"를 return하는 solution 함수를 완성해주세요.

⚠️ 제한사항

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

✅ 풀이

☝️ 첫 번째 풀이 (실패)

문제를 풀기위해 풀이를 생각한 흐름은 다음과 같다.

• goal의 원소들을 합한 문자열에 cards1과 cards2의 원소들이 포함되어 있어야 한다.
• 포함되어 있는지 판단할 때 정규식을 사용하면 편하겠는걸?
  • "aaa"와 "bbb"가 문자열 내부에 포함되어 있는지를 판단할 수 있는 정규식은 .*aaa.*bbb.* 이다.
  • 배열의 문자열을 합해 문자열을 반환해주는 joinToString을 사용하자.

class Solution {
    fun solution(cards1: Array<String>, cards2: Array<String>, goal: Array<String>): String {
        val cards1Regex = cards1.joinToString(".*", ".*", ".*").toRegex()
        val cards2Regex = cards2.joinToString(".*", ".*", ".*").toRegex()
        val strGoal = goal.joinToString("")
        
        return if (cards1Regex.matches(strGoal) && cards2Regex.matches(strGoal)) "Yes" else "No"
    }
}

결과는 실패했다. 내가 간과했던 점은 모든 cards 내의 원소들을 사용할 필요가 없다는 것이고, 주어지는 goal은 이미 cards1과 cards2의 원소들로만 구성되어 있다는 것이었다.

✌️ 두 번째 풀이 (실패)

정규식으로도 풀.. 수 있었을까? 확실한 건 지금 나의 지식으로는 정규식을 계속 붙잡고 있는건 시간 낭비라는 것이다. 그래서 다른 방법을 생각해보았다. 이번에는 다음과 같은 흐름으로 풀어보았다.

• 카드들이 순서대로 사용되어야 하니까, goal에 있는 단어들의 cards1(혹은 cards2)에서의 인덱스가 오름차순이어야 한다.
• 모든 카드를 사용할 필요는 없으니, 사용된 카드의 인덱스만 확인하자.
• 오름차순인 것을 확인하려면, 오름차순으로 정렬하기 전과 정렬 후의 배열이 같아야 한다.

class Solution {
    fun solution(cards1: Array<String>, cards2: Array<String>, goal: Array<String>): String {
        var cards1Idx = goal.filter { cards1.contains(it)}.map { cards1.indexOf(it) }
        var cards2Idx = goal.filter { cards2.contains(it)}.map { cards2.indexOf(it) }
        
        return if ((cards1Idx == cards1Idx.sorted()) && (cards2Idx == cards2Idx.sorted())) "Yes" else "No"
    }
}

그렇다. 이번에도 실패했다. 내가 또!! 간과했던 점은 중간에 건너뛰는 카드가 있으면 안된다는 것이다! 위의 코드로는 건너뛰는 카드가 있더라도 Yes를 반환한다. 아오 문제를 제대로 좀 읽고 풀자.

👌 세 번째 풀이 (성공)

세 번째에는 다음과 같이 생각하면서 풀이했다.

• goal의 원소들을 순서대로 확인한다.
  • 두 카드 배열의 첫번째 원소들과 확인 중인 goal의 원소와 같은 원소가 있는지 확인한다.
    • 있다면, 해당 배열의 첫번째 원소를 drop 한다.
    • 없다면, goal을 만들 수 없는 것이므로 No를 반환한다.
    • goal의 끝까지 살펴봤다면, goal을 만들 수 있는 것이므로 Yes를 반환한다.
• 매개변수로 받은 배열은 재할당이 불가하다.
  • 새로 만든 변수에 대입 후 사용하자.
• drop을 사용하면 list 형이 된다.
  • 배열로 형변환을 해주자.
• drop을 반복하면, 배열의 길이가 0인 경우가 생긴다.
  • isEmpty로 배열이 빈 배열인지 확인해야 한다.

class Solution {
    fun solution(cards1: Array<String>, cards2: Array<String>, goal: Array<String>): String {
        var (c1, c2) = Pair(cards1, cards2)
        for (word in goal) {
            if (!c1.isEmpty() && c1[0] == word) c1 = c1.drop(1).toTypedArray()
            else if (!c2.isEmpty() && c2[0] == word) c2 = c2.drop(1).toTypedArray()
            else return "No"
        }

        return "Yes"
    }
}

나는 잦은 형변환을 싫어한다. 뭔가뭔가.. 성능에 이슈가 있을 것 같이 생겼기 때문이다. 그래서 성공은 했지만 이번에도 꾸역승의 느낌이 있어서 다른 사람들의 풀이를 더 열심히 찾아봤다.

🔥 다른 사람의 풀이

세 번째 풀이의 방식으로 푼 사람들이 많았다. 다만, 배열의 첫 원소를 날려버리는 게 아닌 인덱스를 하나씩 올려가며 푼 풀이가 있었다.

class Solution {
    fun solution(cards1: Array<String>, cards2: Array<String>, goal: Array<String>): String {
        var idx1 = 0
        var idx2 = 0
        goal.forEach {
            if (idx1 < cards1.size && it == cards1[idx1]) idx1++
            else if (idx2 < cards2.size && it == cards2[idx2]) idx2++
            else return "No"
        }
        return "Yes"
    }
}

이렇게 하면 배열로 바꾸지 않아도 돼서 더 좋은 방식이라 생각했다.

💭 후기

분명 문제를 제대로 읽었다 생각했는데 풀이를 하다보면 하나씩 빼먹는 것 같다. 이제까지는 어떻게 풀어야 하지?를 먼저 생각하기 보다 냅다 코드 먼저 작성해서 풀었었는데, 이번 문제는 생각을 먼저하고 풀게 되더라.. 아마 코드로 반환값 확인해가면서 푸는 방식에 익숙해져 있어서 생각 먼저 하다보니 여러가지 조건을 놓친게 아닐까하는 생각이 든다. 내일도 만약 이런 문제가 있다면 꼼꼼히! 꼭!! 꼼꼼히!!! 풀이해야겠다.