[Leetcode] 2901. Longest Unequal Adjacent Groups Subsequence II

 

역시 Computational Thinking 정수는 Dynamic Programming 문제 유형이다.

많이 풀어보고 익숙해지지 않으면 발상하기 쉽지 않은 사고 방식이라 더욱 매력적이다.

오랜만에 재밌는 문제였다.

 

이런 유형 문제를 많이 풀어보고 싶다는 생각까지 들었다.

물론 퇴근하고 여기에 갖다 바친 내 3시간은 전혀 재밌지 않다.

사실 설명 자체가 DP 유형 문제 만들기 위해 어거지로 써놓은 느낌도 있고.

 

비슷했던 어제 문제 설명도 별로였는데, 오늘은 정말 X판이군이라는 평가

 

 

문제 설명

문자열 배열 words와 정수 배열 groups가 주어진다.
두 배열의 길이는 동일하며 각각의 인덱스 i는 하나의 단어와 해당 단어의 그룹을 나타낸다.

우리는 [0, 1, ..., n-1]의 인덱스 중 일부를 골라 최장 부분수열(subsequence)을 선택해야 한다.
단, 다음 조건을 만족해야 한다:

1. 인접한 인덱스들의 그룹이 서로 달라야 한다.
   • 즉, groups[i] != groups[i+1]
2. 인접한 인덱스들의 단어 길이가 같고, 해밍 거리(Hamming Distance)가 정확히 1이어야 한다.
   • 해밍 거리: 같은 길이의 문자열에서 서로 다른 위치의 개수

선택된 인덱스들의 순서대로 대응되는 words들을 반환하라.
여러 정답이 가능할 경우 그 중 하나를 반환하면 된다.

예시

• 예제 1
  입력: words = ["bab", "dab", "cab"], groups = [1,2,2]
  출력: ["bab", "cab"]
  설명:
  • 후보 subsequence: [0,2]
  • 그룹이 다르고, "bab"과 "cab"의 해밍 거리는 1 → 조건 만족
  • [0,1] 또한 유효하며 길이 2가 최대임
• 예제 2
  입력: words = ["a","b","c","d"], groups = [1,2,3,4]
  출력: ["a","b","c","d"]
  설명:
  • 모든 단어 길이 동일
  • 그룹 모두 다름
  • 인접한 단어 간 해밍 거리 모두 1 → 전체 수열 가능
  • 최장 길이 4

조건(제약사항)

• 1 ≤ n ≤ 1000
• 1 ≤ words[i].length ≤ 10
• 1 ≤ groups[i] ≤ n
• words는 중복 없는 문자열로 구성됨
• 각 단어는 소문자로만 구성됨

풀이전략

여러 풀이가 있겠지만 나는 Dynamic Programming 으로 풀었다.

i 위치에서 최대 길이는 i 보다 작고 조건을 만족하는 임의의 위치 j 까지 최대 길이에 1을 더한 값이다.

물론 이러한 j 에 대한 비교를 여러 번 수행할 예정이기 때문에 정확히는 $DP[i] = max(DP[i], DP[j] + 1)$ 이 된다.

 

여기서 중요한 점은 정답인 Case의 실제 원소 값을 추적해야 한다는 점이다.

DP 문제를 풀 때 자주 사용되는 테크닉을 하나 소개한다.

바로, DP가 업데이트 되는 순간에 연결된 정보를 PATH 배열에 함께 저장해주는 알고보면 대단하지 않은 방법이다.

 

모두 -1로 초기화된 경로 배열에 이전 위치 정보를 저장하면, 정답인 경로를 따라서 추적할 수 있다.

탈출 조건은 -1 값으로 잡아주자.

 

class Solution:
    def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        n = len(groups)
        dp = [1 for _ in range(n)]
        path = [-1 for _ in range(n)]
        t_idx = 0

        for i in range(n):
            # max length of position i = previous position j + 1
            for j in range(0, i):
                if dp[i] < dp[j] + 1 and self.check(words[i], words[j], groups[i], groups[j]):
                    dp[i] = dp[j] + 1
                    path[i] = j

                    if dp[t_idx] < dp[i]:
                        t_idx = i

        ans = []

        # finding path from dp
        while t_idx != -1:
            ans.append(words[t_idx])
            t_idx = path[t_idx]

        # reverse order
        return [x for x in ans[::-1]]

    def check(self, w1, w2, g1, g2):
        if g1 == g2 or len(w1) != len(w2):
            return False
        cnt = 0
        for ch1, ch2 in zip(w1, w2):
            cnt += ch1 != ch2
        return cnt == 1