2021-02-04] Longest Harmonious Subsequence

오늘의 문제:

leetcode.com/explore/featured/card/february-leetcoding-challenge-2021/584/week-1-february-1st-february-7th/3628/

 

 

harminious subsequence를 정의하자면, 특정 값과 인접한 수( if N=2 / 1,3 )를 포함한 부분집합을 의미하고

return 값으로는 이 부분집합들의 최대로 긴 값을 리턴하는 것이다.

 

예시 1번을 천천히 뜯어보자.

 

nums=[1,3,2,2,5,2,3,7] 의 조화로운 부분집합은

 

1) [1,2,2,2] 길이 = 4

2) [3,2,2,2,3] 길이 = 5

 

두 개 뿐이다. ( 5,7 은 인접한 수가 없다. ) 그래서 1번 답은 5이다.

 

예시 2번은 [1,2],[2,3],[3,4] 3개의 후보가 나오고 길이가 모두 같이 2여서 답은 2이다.

 

인접한 수가 없으면 0을 반환한다.

 

양쪽을 생각할 필요 없이 N , N-1로 생각하면 편하다. ( 어차피 N=2일때 (1,2),(2,3) / N=3일때 (2,3),(3,4) 중복되게 검사 )

 

python에서는 Counter라는 좋은 함수가 있다. dictionary 형태로 list의 값을 key값으로 value는 중복횟수를 넣어준다. 

 

그 후 key값을 을 비교하여 value를 더하고 가장 큰 값을 반환하면 된다.

 

이렇게 되면 counter로 만들어지며 O(N)에 해당하는 상수시간의 알고리즘이 나온다.

 

broute force로는 O(n)이라 가능하지만, 주어지는 list의 최대 길이가 10^9까지 나와

 

Time limited에 걸려 dictionary 방식을 사용한다. ( 필자는 Time limited 에 걸렸다 )

 

아래 코드를 보며 이해해 보면 좋을 것 같다.

 

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        c= Counter(nums) # 입력된 list의 값을 key로 중복횟수를 value 값에 넣어 반환
        keys = c.keys()
        maxval = 0
        for num in keys:
            if num - 1 in keys: # num+1을 굳이 검사할 필요 없음
                if c[num - 1] + c[num] > maxval: # 기존 max값과 비교하는 구문
                    maxval = c[num - 1] + c[num]
        return maxval