LeetCode (5) 썸네일형 리스트형 [Leetcode] 128번 - 가장 긴 연속하는 수의 개수 1. 문제 파악문제 링크: https://leetcode.com/problems/longest-consecutive-sequence문제 요구사항: 주어진 배열에서 연속된 요소의 개수를 세서 반환해라시간복잡도: O(N) 내에 풀라고 명시 -> 정렬 알고리즘은 못쓴다. 2. 핵심 문제 풀이 도출 일단, O(N) 내에 풀라고 명시했기 때문에, O(NlogN)인 정렬 알고리즘은 못쓴다. 배열을 한 번 순회하면서 연속된 수 체크해야한다. 그렇다면 정렬 없이 빠르게 값의 포함 여부를 확인하는 자료구조가 필요하다. HashTable 자료구조를 기반으로 하는 HashSet이나 HashMap 자료구조는 평균 O(1) 내에 가능하다. 따라서 해당 자료구조로 문제 풀이를 접근해본다. 배열을 순회해서 저장한 HashTable.. [Leetcode] 347번 - Top K Frequent Elements (using Array) 1. 문제 파악문제 링크: https://leetcode.com/problems/top-k-frequent-elements/문제: 주어진 배열의 요소값중에서 빈도수가 가장 높은 요소를 k개 저장한 배열을 반환해라.시간복잡도 파악: 입력크기가 100000이라서 O(N\logN) 이내어야한다.문제 나눠서 정의배열을 순차적으로 조회하면서 요소별로 빈도수 연산 -> 가장 빈도수가 큰 요소들을 반환해야하므로 동적으로 빈도수 연산을 하지못한다. 따라서 각 요소별로 모든 빈도수를 계산하고 key, value를 상요하는 자료구조에 저장해야한다.자료구조를 빈도수 크기로 정렬한다. (단, 빈도수가 중복되는 요소값이 존재한다.)정렬된 자료구조에서 k개 만큼 값을 가져와서 반환 배열에 저장 2. 핵심 문제 풀이 도출배열을 순.. [Leetcode] 238번 - Product of Array Except Self 1. 문제 파악문제 링크: https://leetcode.com/problems/product-of-array-except-self/description/문제: 자기 자신을 제외한 주어진 배열의 모든 요소의 곱셈을 저장한 배열 반환시간복잡도 파악: 입력 크기가 10000개 이내라서 O(N log N)이하면 되지만, 문제에서 O(N)이내로 해결하라고 명시되어 있다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출배열을 순차적으로 조회한다.현재 조회하는 요소가 아닌 모든 요소의 곱을 반환할 배열에 저장한다.위의 로직대로라면 O(N^2)시간이 걸린다. 2. 핵심 문제 풀이 도출시간복잡도가 O(N) 내에 해결해야하므로, 배열 조회할때 반환할 배열의 연산(계산과 저장) 끝나야한다. 배열 조회 시간이 O(N)이기 .. [Leetcode] 5번 - 최대길이 palindromic 부분 문자열 문제 링크: https://leetcode.com/problems/longest-palindromic-substring/description/1. 문제 파악문제를 나눠서 정의: 주어진 문자열의 substring 중에서 대칭되는 것중에서 가장 긴것 찾기주어진 문자열에서 좌우 대칭되는 substring 찾기좌우 대칭되는 substring 중에서 제일 긴 것 찾기시간복잡도 파악: 1 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상2. 핵심 문제 풀이 도출문제를 나눈것에 대해 풀이를 도출해본다.좌우 대칭되는 문자열의 중앙값 부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)모든 substring에서 가장 긴 좌우 대칭 문.. [LeetCode] 3번 – 중복 없는 가장 긴 부분 문자열 (Java, 슬라이딩 윈도우 풀이) 1. 문제 파악해당 문제 유형은 단순히 구현이나 자료구조와 알고리즘을 아는 것보다 동작을 추상화해서 수식 또는 알고리즘으로 모델링하는 것이 핵심이다.문제 링크: https://leetcode.com/problems/longest-substring-without-repeating-characters문제 정의:주어진 문자열의 substring에서 알파벳이 중복되지 않는 문자열 찾기중복되지 않는 substring 중에서 제일 긴거를 찾기문제의 제약 파악 (입력값 크기, 상수 조건)0 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출중복 문자가 없는 substring을 찾을려면, 중첩 반복문으로 하나의 문자를 지정하고 나머지 문자들을 확인해야한다. 그러면 n + n-1 + n-2 + ... = n(n+1)/2 .. 이전 1 다음