HwangHub

🤔 Intuition 체감상 어려워서 답을 참고했다. 막상 답을 보면 "간단하네..." 하는 문제를 마주하면 현타가 좀 오는데, 이번 문제도 그러했다. counting array를 운영하는 부분수열 유형이므로 투포인터로 해결할 수 있음은 명료하다. 🔎 Algorithm & Complexity * @algorithm two pointer * @time O(N) * @memory O(N) 👨🏻‍💻 Logic 직관적이면서 가장 빠른 풀이는 maxEnd와 minEnd를 운영하는 것이다. (3 ms) right pointer를 +1씩 옮겨가면서 정확히 K개의 distinct elements로 구성된 가장 작은 subarray를 먼저 찾고, (right=minEnd) righter pointer를 그 상황에서 di..

🤔 Intuition 특정 element의 개수를 세가면서 부분수열의 개수를 구하는 문제이므로 투포인터 문제임을 알 수 있다. 🔎 Algorithm & Complexity * @algorithm two pointer * @time O(N) : 10ms * @memory O(N) : 61.12 MB 👨🏻‍💻 Logic 중요 포인트는, right를 증가시키다가, max element가 k번 등장하는 경우에 "nums의 총 길이 - right의 index"를 연산하여 "max element가 k번 보다 더 많이 등장하는 경우의 수"를 단 한번의 연산으로 구해내는 작업이었다. 이를 통해 추가적인 포인터 이동 연산 없이 O(N)으로 문제를 해결할 수 있었다. public class LeetCode_2962 { /..