본문 바로가기
알고리즘 문제/Leetcode

[leetcode][594] Longest Harmonious Subsequence.cpp

by 햄과함께 2021. 2. 4.
320x100

문제 : leetcode.com/problems/longest-harmonious-subsequence/


배열이 주어질 때, 최대값과 최소값이 정확히 1차이가 나는 subsequence들의 최대 길이를 구해라.


결국 길이가 1차이나는 요소들의 발생횟수들의 합의 최대값을 구하는 문제.

배열을 탐색하면서 요소 값을 key, 나온 횟수를 value로 가지는 map을 만들어 갱신한다.

map을 모두 채웠으면 map을 모두 탐색하면서 탐색중인 map의 key값 + 1을 map에서 찾아서 만약 없으면 최대, 최소 차이가 1인 서브시퀀스를 만들수 없으므로 다음 map요소를 탐색한다. 만일 있다면 map[key] + map[key+1] 한 값들의 최대값을 구하면 정답이 된다.

 

시간복잡도는 O(N). N은 배열의 길이.


소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/594.%20Longest%20Harmonious%20Subsequence.cpp


map<int, int> m;
for(map<int,int>::iterator it = m.begin();
    it != m.end(); it++) {
    int first = it->first;
    int second = it->second;
     //...
}
map<int, int> m;
for(auto now: m) {
   int first = now.first;
   int second = now.second;
     //...
}

iterator 반복문 항상 위에처럼 썼었는데 아래처럼 auto 쓰면 for문 쉽게 접근 가능하구나. 개꿀.

320x100

댓글