본문 바로가기

Coding Test

 (34)
[Leetcode] 19번 - Remove Nth Node From End of List 1. 문제 파악문제 링크: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/문제: 마지막 노드로부터 n번째 노드를 삭제하고 head를 반환해라.시간복잡도 파악: 연결리스트의 입력 크기가 30이라서 O(N) 이내어야한다. 2. 입출력 케이스 도출일반 케이스: head = [1,2,3,4,5], n = 2 -> [1,2,3,5], head = [1,2], n = 1 -> [1]엣지 케이스: head = [1], n = 1 -> [], head = [1,2], n = 2 -> [2] 3. 핵심 문제 풀이 도출연결리스트의 끝에서 n번째 노드를 삭제하는 것이다. 그래서 나는 스택 자료구조가 떠올랐다. 스택에 연결리스트 노드를..
[Leetcode] 143번 - Reorder List 1. 문제 파악문제 링크: https://leetcode.com/problems/reorder-list/문제: L0 → L1 → … → Ln - 1 → Ln 수열인 연결 리스트를 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …로 재정렬해라.시간복잡도 파악: 입력크기가 50000이라서 O(nlogn) 이내어야한다. 2. 입출력 케이스 도출짝수: [1 2 3 4]홀수: [1], [1 2 3 4 5 6 7] 3. 핵심 문제 풀이 도출 양쪽 끝 투 포인터(left, right) 사용해서 연결 리스트를 재정렬할수있다. 여기서 left와 right는 기존 리스트의 노드 순서를 가리킨다.EX1) [1, 2, 3, 4][1, 2, 3, 4]: left = L1, right = L4Logic: ..
[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] 647번 - palindromic substring 문제 링크: https://leetcode.com/problems/palindromic-substrings/1. 문제 파악문제를 나눠서 정의: 주어진 문자열의 substring 중에서 좌우 대칭되는 개수 구하기주어진 문자열에서 좌우 대칭되는 substring 찾기좌우 대칭되는 substring을 카운트 하기시간잡도 파악: 1 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상 2. 핵심 문제 풀이 도출문제를 나눈것에 대해 풀이를 도출해본다.좌우 대칭되는 문자열의 중앙값부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)모든 substring중에서 좌우 대칭되는 것을 카운팅해야되기 때문에, 모든 문자를 중앙값으로 두고 좌..
[Leetcode] 49번 - 그룹 애나그램(Anagrams) 문제 링크: https://leetcode.com/problems/group-anagrams/description/ 1. 문제 파악 애나그램(Anagram): 동일한 문자의 조합으로 이루어진 문자열이면 동일한 값으로 치부문제를 나눠서 정의: 주어진 문자열 배열에서 애나그램인 문자열 끼리 리스트로 묶어서 반환해라.문자열끼리 애나그램 판별애나그램인 문자열끼리 리스트에 추가시간복잡도 파악:1 -> 문자열 배열의 길이: 10000 -> O(nlogn)0 -> 문자열의 길이: 100 -> O(n)시간 복잡도 총합: O(n x nlogn) 2. 핵심 문제 풀이 도출 문제를 나눈것에 대해 풀이를 도출해본다.애나그램 판별은 어떻게 할까? -> 문자열에서 문자의 개수가 동일한지 확인 -> 너무 복잡 -> 정렬을 하면..
[Leetcode] 5번 - 최대길이 palindromic 부분 문자열 문제 링크: https://leetcode.com/problems/longest-palindromic-substring/description/1. 문제 파악문제를 나눠서 정의: 주어진 문자열의 substring 중에서 대칭되는 것중에서 가장 긴것 찾기주어진 문자열에서 좌우 대칭되는 substring 찾기좌우 대칭되는 substring 중에서 제일 긴 것 찾기시간복잡도 파악: 1 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상2. 핵심 문제 풀이 도출문제를 나눈것에 대해 풀이를 도출해본다.좌우 대칭되는 문자열의 중앙값 부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)모든 substring에서 가장 긴 좌우 대칭 문..

티스토리툴바