[LeetCode] #594. Longest Harmonious Subsequence

문제 :

 

사실 이 문제는 저번주에 시도했던 문제이지만 풀어내지 못했다. 런타임이 말도 안되게 길게 나왔는지 자꾸 RuntimeExceptionError가 발생했다. 그런데 오늘은 정말 한번의 시도만에 풀어버려서 사실 살짝 놀랐다 ㅎㅎ 한달째 꾸준히 하루에 2-3문제씩 알고리즘을 푸는 중인데 뭔가 문제를 풀면 풀수록 어떠한 자료구조를 써야 하는지가 생각난다. 작년 이맘때쯤엔 같은 문제를 봐도 뭐가 뭔지 몰랐고 정말 막막했지만, 이젠 뭔가 자료구조 정도는 생각해 낼 수 있다. 

 

----

어쨌든! 이 문제는 간단하다. 정수타입의 리스트가 주어지고, 저 리스트에서  maximum Harmonious subsequece의 길이를 구하는것이다. 여기서 maximum Harmonious subsequece란, 배열에서 최댓값과 최솟값의 차이는 1이여야 한다. 그러한 배열들의 가장 긴 길이를 리턴하면 된다.

 

※처음 든 생각:

- brute force를 생각했다. 사실 이걸 brute force로 풀면 말도안되는 런타임이 나올것이다. 아마 작년 이맘때쯤 이 문제를 못 풀었던 이유도 비슷한 이유가 아닐까 싶다. 하지만 이건 말도안되는 방법이므로 패스! 물론 이렇게 푼다해도 통과는 하겠지만, 실제 코테에서는 이런식으로 푼다면 다른 사람들에게 밀릴것이다.

 

- 우리가 필요한것은 결국 max length이고, 배열의 길이는 그 배열 요소의 출현 횟수(frequency)에 정비례 한다. 위의 1번 예시에서, 저중 두 수의 차이가 1인 숫자들의 조합은 (1, 2), (2, 3) 이다. 이걸 조합이 아니라 배열의 관점에서 본다면 [1,2,2,2], [2,2,2,3,3] 이다. 이 두 배열중 길이가 더 긴 후자의 배열 == 5 를 리턴하면 된다. 

 

- 길이(==frequency)가 필요하다면, 각 요소의 출현 횟수를 저장할 수 있는 딕셔너리를 선언해준다. 

 

자 그럼, 아래는 내가 제출해 통과한 코드이다.

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        dict ={}
        maxLen = 0

        nums.sort()

        for i in nums:
            if i in dict:
                dict[i] += 1
            else:
                dict[i] = 1

        keys = list(dict.keys())
        
        for i in range(len(keys) - 1):
            current_key = keys[i]
            next_key = keys[i + 1]
            if next_key - current_key == 1 and (dict.get(current_key) + dict.get(next_key) > maxLen):
                maxLen = dict.get(current_key) + dict.get(next_key)
        
        return maxLen

 

- 먼저, 빈 딕셔너리를 선언하고, max길이를 찾을 때마다 계속 업데이트 해 줄 maxLen이라는 변수를 0으로 초기화 해 준다.

 

- 다음으로 nums.sort()를 해준 이유는 다음과 같다;  배열을 정렬하여 현재 값과 다음값이 1이 차이날때만 나머지 로직을 수행 하도록 해 주었다. 정렬을 하면 현재 값과 다음값의 차이가 1이 아니라면 그 이후의 요소들은 무시 할 수 있다. 정렬된 배열은 오름차순으로 정렬되므로 이미 다음값과 현재값의 차이가 1이 아니라면 그 다음의 값들은 1 이상 차이날것이다.

 

- 이제 선언한 딕셔너리에 각 요소와 그 요소의 출현 횟수를 매핑 시켜준다. 나는 (숫자 : 출현횟수)와 같이 매핑 시켜 주었다.

 

- 다음으로, 현재값과 다음값의 차이가 1인지를 비교하려면 딕셔너리의 키값들을 가져와야 한다. list(dict.keys())를 이용해 딕셔너리의 키값들을 리스트로 받아오고, 키값들을 순회한다. 순회할때는 두가지 조건이 있다. 1. (다음 key값 - 현재 key값)이 1인경우 AND 두 요소의 value값을 더했을때(두 요소의 출현 횟수를 더한 값은 두 요소를 배열로 만들었을때의 길이와 같다.), 이 값이 현재 maxLen보다 클때만(어차피 현재 길이가 maxLen보다 작다면 아무것도 할 필요가 없다) maxLen을 업데이트 해 주고, 마지막에 maxLen을 리턴 해 준다.

 

아래는 내가 받은 report이다.