URL : https://leetcode.com/problems/longest-harmonious-subsequence/description/
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
1. 문제 설명
먼저 문제를 읽어보겠습니다..
We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1. Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences. A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].
Example 2:
Input: nums = [1,2,3,4]
Output: 2
Example 3:
Input: nums = [1,1,1,1]
Output: 0
Constraints (제약조건)
1 <= nums.length <= 2 * 104
-109 <= nums[i] <= 109
가장 긴 Harmonious Subsequence, 즉 LHS(Longest Harmonious Subsequence)를 찾으라는 문제입니다! 이 LHS라는 것이 무엇인지, 문제에 나온 설명을 통해 파악하고, 친숙화하는 시간을 가지도록 하겠습니다. 문제 풀이에 앞서 이 LHS라는 것을 이해하지 못하면 문제 풀이 자체가 불가능할 테니까요.
1.1 Subsequence의 정의
일단 Subsequence라는 것에 대해서 알아 볼까요? subsequence라는 것이 무엇인지 다음과 같이 설명이 되어 있습니다.
A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
음.. 원래 배열에서 어떤 원소에서 특정 원소를 삭제하거나 (혹은 삭제하지 않거나) 해서 새롭게 만든 배열인데, 중요한 것은 순서가 변경되지 않아야 합니다! 문장을 읽어도 이해가 되지 않을 테니, 예를 들어볼까요?
array = [1,3,2,2,5,2,3,7] 이라고 하였을 때, 어떤 것들이 이 array의 subsequence가 될 수 있는 지를 알아 봅시다.
array = [1,3,2,2,5,2,3,7] → subsequence = [1,3,2,2,5,2,3,7]
array = [1,3,2,2,5,2,3,7] → subsequence = [1,2,2,5,7]
array = [1,3,2,2,5,2,3,7] → subsequence = [3,2,3,7]
array = [1,3,2,2,5,2,3,7] → subsequence = [1,2,5,2]
array = [1,3,2,2,5,2,3,7] → subsequence = []
array의 subsequence가 될 수 있는 후보로는 위와 같은 것들이 될 수 있습니다. 왜냐하면! 원소를 삭제하거나, 혹은 삭제하지 않고 오로지 가져오는 순서만 지킨다면 그것이 바로 subsequnce이기 때문이죠.
1.2 Harmonious Subsequence의 정의
Subsequence에 대해서 알아 보았으니, 이제는 Harmonious Subsequence에 대해서 알아보겠습니다. Harmonious Subsequence라는 것은, 위와 같은 Subsequence 중에서, 최대값과 최소값의 차이가 1인 조건을 만족하는 특수한 subsequence라고 정의 되어있습니다. 이것도 예를 한번 들어 볼까요?
array = [1,3,2,2,5,2,3,7] → subsequence = [3,2,2,3] → Harmonious Subsequence 만족!
array = [1,3,2,2,5,2,3,7] → subsequence = [1,3,2,2,7] → Harmonious Subsequence 불만족!
array = [1,3,2,2,5,2,3,7] → subsequence = [1,2,2] → Harmonious Subsequence 만족!
array = [1,3,2,2,5,2,3,7] → subsequence = [2,3] → Harmonious Subsequence 만족!
array = [1,3,2,2,5,2,3,7] → subsequence = [5,2,7] → Harmonious Subsequence 불만족!
2번과 5번 같은 경우는, Subsequence이지만, subsequence내에 존재하는 원소의 최대값과 최소값의 차이가 1이 아니기 때문에, Harmonious Subsequence가 아닙니다. 우리의 목표는, 주어진 array에서 가장 긴 조화순열, 즉 LHS를 찾는 것입니다. 그러면 이 LHS를 어떻게 하면 찾을 수가 있을까요? 이 LHS를 O(N)이라는 시간복잡도에 찾을 수 있는 알고리즘이 존재합니다. 이 알고리즘의 기반을 이루는 아이디어를 살펴보겠습니다.
2. 문제 해결
2.1 문제 해결의 아이디어
array로부터 subsequence를 만들었을 때 그 subsequence가 harmonious subsequence이려면 어떠한 조건이 붙어야 할까요? 오로지 subsequence에 두 가지 종류의 원소가 존재하면서, 이 두 원소의 차이가 1이 될 때 그 순열은 조화순열이 됩니다. 정말 그런지 알아 볼까요?
array = [1,3,2,2,5,2,3,7] → subsequence = [3,2,2,3] → Harmonious Subsequence 만족!
array = [1,3,2,2,5,2,3,7] → subsequence = [1,3,2,2,7] → Harmonious Subsequence 불만족!
array = [1,3,2,2,5,2,3,7] → subsequence = [1,2,2] → Harmonious Subsequence 만족!
array = [1,3,2,2,5,2,3,7] → subsequence = [2,3] → Harmonious Subsequence 만족!
array = [1,3,2,2,5,2,3,7] → subsequence = [5,2,7] → Harmonious Subsequence 불만족!
array = [1,3,2,2,5,2,3,7] → subsequence = [2,2,5,2] → Harmonious Subsequence 불만족!
위에서 가져온 예를 재탕해보겠습니다. 조화순열이 되는 1,3,4,번의 경우 부분순열 내에 오로지 두 가지의 원소가 존재하며 이 두 원소의 차이는 1입니다. 그러나 조화순열 조건을 만족하지 않는 2, 5번의 경우 부분순열 내에 세 가지 이상의 원소가 존재합니다. 그리고 6번의 경우처럼 오로지 두 가지 원소가 존재하더라도, 그 두 원소의 차이가 1이 아니라면 조화순열이 되지 못합니다.
그러면 주어진 array내에서 오로지 두 원소를 지니면서 그 두 원소간의 차이가 1인 subsequence중 가장 긴 것을 찾으면 게임은 끝납니다. 빨리 끝났으면 좋겠군요.
2.2 아이디어를 어떻게 구현하지?
자, 우리의 목표는 다음을 찾는 것입니다.
" 주어진 array내에서 오로지 두 원소를 지니면서 그 두 원소간의 차이가 1인 subsequence중 가장 긴 것 "
이건 또 어떻게 찾을까요? 찾을 수 있는 아주 간단한 방법이 있습니다. 전혀 위 상황과 관련이 없어 보이는 HashMap이라는 자료구조를 이용하는 것입니다. 이걸 이용해서 어떻게 찾는 지 찬찬히 알아보겠습니다.
array = [1,3,2,2,5,2,3,7]
이런 array가 주어졌다고 해 보겠습니다. array에 어떠한 원소들이 있는 지 살펴 볼까요?
살펴보니, array에는 1, 2, 3, 5, 7이라는 원소가 존재합니다.
그러면 우리는 다음의 경우들을 모두 고려하면 위 파란색 문장을 만족시키는 부분순열을 찾을 수가 있습니다.
원소 1, 2로만 이루어진 subsequence중 가장 긴 것의 길이
원소 2, 3로만 이루어진 subsequence중 가장 긴 것의 길이
원소 3, 4로만 이루어진 subsequence중 가장 긴 것 → 이런 순열은 존재 X 왜냐하면 array에 4가 없기 때문
원소 5, 6로만 이루어진 subsequence중 가장 긴 것 → 이런 순열은 존재 X 왜냐하면 array에 6가 없기 때문
원소 7, 8로만 이루어진 subsequence중 가장 긴 것 → 이런 순열은 존재 X 왜냐하면 array에 8가 없기 때문
그러면 위 두 가지는 어떻게 구할 수 있을까요? 바로 다음과 같이 구할 수가 있습니다.
원소 1, 2로만 이루어진 subsequence중 가장 긴 것의 길이 → array에서 1과 2의 총 개수
원소 2, 3로만 이루어진 subsequence중 가장 긴 것의 길이 → array에서 2와 3의 총 개수
엇, 그런데 원소 1과 2로만 이루어진 부분순열 중 가장 긴 것의 길이가 왜 위와 같이 계산이 될 수 있나요??라는 의문이 들 수 있습니다. 직관적으로 왜 이렇게 되는지 예를 들어서 또 알아보겠습니다!
- 원소 1, 2로만 이루어진 subsequence중 가장 긴 것을 찾아보자.
array = [1,3,2,2,5,2,3,7] → subsequence = [1,2,2,2] → 총 길이는 1의 개수 + 2의 개수 = 4
- 원소 2, 3로만 이루어진 subsequence중 가장 긴 것을 찾아보자.
array = [1,3,2,2,5,2,3,7] → subsequence = [3,2,2,2,3] → 총 길이는 2의 개수 + 3의 개수 = 5
분명 LHS의 길이를 구하라는 무시무시한 문제였는데, array에서 특정 원소의 개수만 세면 되는 매우 간단한 문제로 변하는 기적같은 일이 일어났습니다! 이것을 소스코드로 구현해 봅시다.
3. 소스 코드
class Solution {
public int findLHS(int[] nums) {
// array에서 각 원소의 개수를 카운트하기 위한 map 선언
Map<Integer, Integer> map = new HashMap<>();
int answer = 0;
// nums의 각 원소의 개수를 센다
for(int num : nums)
map.put(num, map.getOrDefault(num, 0) + 1);
// nums에서 오로지 두 원소로 이루어진 LHS의 길이를 세기 위한 작업
// nums = [1,3,2,2,5,2,3,7] 이라면
// 1 개수 + 2 개수 / 2 개수 + 3 개수 / 3개수 + 4 개수 / 5 개수 + 6 개수 / 7 개수 + 8 개수
// 이 중에서 가장 큰 값을 찾으면 그것이 바로 LHS의 길이가 된다.
for(int n : map.keySet()) {
if(map.containsKey(n+1))
// 최대길이 갱신
answer = Math.max(answer, map.get(n) + map.get(n+1));
}
// 정답 리턴
return answer;
}
}'Algorithm[Java] > Hash Table' 카테고리의 다른 글
| Determine if Two Strings Are Close [Java / LeetCode 1657] (0) | 2024.01.26 |
|---|
