•
문제 설명 : 문제에서 제공하는 Harmonious Subsequence 조건에 맞는 하위 배열 중 가장 긴 길이를 반환하는 것이다.
•
풀이 방법
◦
Sorting 문제이기 했지만, Sorting은 최소 O(NlogN) 이기 때문에 solved도 해시 테이블을 사용한 방식으로 진행했다.
•
시간복잡도 :
•
성공 코드(해시 테이블 사용 방식)
from collections import Counter
class Solution:
def findLHS(self, nums: List[int]) -> int:
nums_count_info = Counter(nums)
result = 0
for k in nums_count_info.keys():
if nums_count_info[k-1]:
result = max(result, nums_count_info[k] + nums_count_info[k-1])
if nums_count_info[k+1]:
result = max(result, nums_count_info[k] + nums_count_info[k+1])
return result
Python
복사
•
성공 코드(sorting 사용 방식)
◦
아래 방식은 sort 사용으로 인해 시간 복잡도가 NlogN 이지만, 공간 복잡도는 해시 테이블 방식에 비해 더 좋은 결과를 보여줄 것이다.
from typing import List
class Solution:
def findLHS(self, nums: List[int]) -> int:
nums.sort()
result = 0
# Harmonious Subsequence 요소 중 작은 숫자에 대한 정보를 저장
prev_count = 0
prev_num = None
current_count = 1
for i in range(1, len(nums)):
# 동일 숫자라면, 현 숫자에 대한 카운팅 증가
if nums[i] == nums[i-1]:
current_count += 1
else:
# 첫 숫자거나, Harmonious Subsequence 중 큰 값이 작은 숫자보다 1이 커서 조건에 맞을 때
# EX) [..., 2, 2, 2, 3, 3, 4 ...] 일 경우
# prev_num은 2, nums[i-1]은 3, nums[i]는 4
if prev_num is not None and nums[i-1] == prev_num + 1:
result = max(result, prev_count + current_count)
# prev -> prev + 1 숫자로 설정
# EX) [..., 2, 2, 2, 3, 3, 4 ...] 일 경우
# 기존 prev_num은 2였지만, 이제 3으로 변경한다.
prev_num = nums[i-1]
prev_count = current_count
# 현 숫자(4)는 다시 1부터 시작한다.
current_count = 1
# 마지막 원소까지 검사한 후에도 prev_num과 nums[-1]을 비교하여 결과를 갱신
if prev_num is not None and nums[-1] == prev_num + 1:
result = max(result, prev_count + current_count)
return result
Python
복사