Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
[LeetCode] 2901. Longest Unequal Adjacent Groups Subsequence II (C++)
EVEerNew 2023. 10. 18. 22:01문제
https://leetcode.com/problems/longest-unequal-adjacent-groups-subsequence-ii/
Longest Unequal Adjacent Groups Subsequence II - LeetCode
Can you solve this real interview question? Longest Unequal Adjacent Groups Subsequence II - You are given an integer n, a 0-indexed string array words, and a 0-indexed array groups, both arrays having length n. The hamming distance between two strings of
leetcode.com
풀이
난이도: Medium
DP를 이용해서 해결하는 문제였다.
아래와 같은 예제를 생각해 보자.
words = ["bad","dc","bc","ccd","dd","da","cad","dba","aba"]
groups = [9,7, 1, 2, 6, 8, 3, 7, 2]
dp[i]는 i번째 word를 포함하고, i번까지로 만들 수 있는 최대 subset이라고 생각하자.
일단 각 dp에 자신을 넣어고,
dp[0] = 'bad"
dp[1] = "dc"
dp[2] = "bc"
dp[3] = "ccd"
dp[4] = "dd"
dp[5] = "da"
dp[6] = "cad"
dp[7] = "dba"
dp[8] = "aba"
dp[i]를 1부터 끝까지, 계산해 둔 dp를 사용해서 구해나간다.
예를 들어
dp[2]는 dp[0]과 dp[1]을 자신에게 이어 붙일 수 있는 지 판단한다.
dp[0] = "bad"로 길이가 맞지 않아 조건 만족되지 않는다.
dp[1] = "dc"로 길이 같고 해밍 거리가 1이며, group도 다르다.
그러므로 dp[1]을 이어 붙여서
dp[2] = { "dc" , "bc" } 가 된다.
dp[j]를 dp[i]에 이어 붙일 때 j와 i가 조건이 맞다면, 이미 dp[j]의 subset도 조건을 만족하고 있기 때문에 그대로 이어 붙일 수 있다.
이처럼 이어 붙였을 때 가장 긴 subset을 만드는 dp를 저장시켜 나가면 문제를 해결할 수 있다.
코드