HARD56 [leetcode][23] Merge k Sorted Lists 문제 : leetcode.com/problems/merge-k-sorted-lists/ k개의 오름차순정렬된 ListNode 포인터 배열이 주어진다. 배열의 모든 ListNode를 오름차순 정렬된 하나의 ListNode로 만들어라. 오름차순 정렬되어있기 때문에 k개의 배열을 탐색하면서 가장 작은 노드를 구하고 이를 정답 리스트노드 다음에 추가한다. 추가한 노드는 다시 탐색되지 않게 하기 위해 next 노드를 보게 갱신한다. 항상 k개의 배열을 탐색하는데, 이를 정답 ListNode를 만들때까지 실행될 것이기 때문에. N = k, M = 정답 ListNode 배열 크기라 할 때, 시간복잡도는 O(NM). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/.. 2021. 1. 26. [leetcode][84] Largest Rectangle in Histogram 문제 : leetcode.com/problems/largest-rectangle-in-histogram/ 히스토그램 바의 높이가 저장된 배열이 주어진다. 히스토그램들로 만들수있는 직사각형의 최대 크기를 구하라. 예시로 주어진 배열로 아이디어를 구체화해보자. 인덱스별 막대바의 높이를 직사각형의 세로길이라 할 때, 구할 수 있는 직사각형의 최대값들을 구한 뒤 이들 중 최대값이 정답이 된다. 직사각형의 세로길이를 배열 값이라 가정해놨기 때문에 하나를 예로 들어서 특정 바의 세로길이로 고정해놨을 때, 최대 직사각형을 구할 수 있는 가로길이를 어떻게 구할수있는지 찾아야한다. 인덱스가 5인 경우를 예로 들어보면 인덱스 5를 포함해서 만들 수 있는 최대 직사각형은 파란색 점선과 같다. 이 때, 인덱스 2를 기준으로 .. 2021. 1. 24. [leetcode][10] Regular Expression Matching 문제 : leetcode.com/problems/regular-expression-matching/ 문자열 s와 패턴 p가 주어질 때 문자열 s가 패턴 p에 매칭되는지 판단하라. 패턴의 경우 나올 수 있는 문자는 총 3가지로, . * 소문자 알파벳 이 있다. . : 어떤 문자가 와도 매칭된다. * : 바로 앞에 나온 패턴 문자와 0개 이상 매칭된다. 소문자 알파벳 : 동일한 문자인 경우 매칭된다. . backtracking으로 구현. 2차원 배열을 만들어 memoization 해줬다. . 과 알파벳 소문자의 패턴인 경우는 문제될게 없다. . 는 무조건 통과이므로 s, p 모두 다음 문자를 확인한다. 소문자 알파벳은 다르다면 false, 같다면 다음 문자를 확인한다. 문제는 *. s = "aaaabb". .. 2021. 1. 22. [Leetcode][128] Longest Consecutive Sequence 문제 : leetcode.com/problems/longest-consecutive-sequence/ 정렬되지 않은 nums 배열이 주어질 때 요소들 중 가장 긴 연속 요소들(ex, 1 2 3 4)의 길이를 구하라. Union find 로 풀었다. nums 배열을 앞에서부터 탐색하면서 탐색중인 숫자를 num이라 할 때, num-1, num+1이 나타난적 있는지 확인한다. 만일 num-1이 이전에 나왔던 숫자라면 num-1와 num의 연속적인 수 중 가장 작은 수들을 가져온다. 이는 부모배열에 저장되어야 한다.(find로 찾는다.) 찾은 부모노드가 다르다면 뒤에 있는 부모노드(num의 부모)를 앞에 있는 부모노드(num-1의 부모)로 갱신하고 연속적인 수들의 최대 길이를 갱신한다.. (union 함수) 다.. 2021. 1. 6. [leetcode][1345] Jump Game IV 문제 : leetcode.com/problems/jump-game-iv/ arr 배열이 주어진다. i 인덱스에서 한 칸 이동한다고 할 때, 총 3가지 위치로 이동할 수 있다. 배열의 범위 내에서 i-1(1), i+1(2)로 이동가능하다. 또한 현재 칸과 같은 값을 가지는 칸(3)으로 이동이 가능하다. 첫 번째 인덱스에서 마지막 인덱스로 이동하는 방법 중 최소의 이동횟수를 구하라. DFS로 풀었다. arr 배열을 탐색하면서 arr 요소값을 인덱스로 하고 인덱스 배열을 value로 만드는 map을 만든다. 인덱스와 탐색횟수를 저장하는 큐를 만들고 {0, 0}을 넣고 큐가 빌 때까지 반복한다. 탐색중인 인덱스가 i라고 할 때, i-1, i+1이 탐색한 적 없다면 큐에 넣는다. 또한 map에 arr[i]를 키 .. 2020. 12. 27. [leetcode] [239] Sliding Window Maximum 문제 : leetcode.com/problems/sliding-window-maximum/ 정수배열 nums 이 주어지고 슬라이딩 윈도우 크기 k가 주어진다. 배열의 맨 왼쪽부터 k개를 유지하면서 오른쪽으로 탐색하는 슬라이딩 윈도우가 있을 때 슬라이딩 윈도우가 오른쪽으로 한 칸 씩 이동할때마다 해당 슬라이딩 윈도우에 있는 요소들 중 가장 큰 값을 가지는 숫자를 배열에 저장해서 반환하라. 우선순위 큐에 요소들을 저장한다. 이 때, nums 요소와 인덱스를 같이 저장한다. 우선순위는 nums 요소(정수)로 판단한다. 만약 탐색 시 탐색 중인 nums 인덱스가 k이상일 때, 우선순위 큐를 탐색하면서 큐의 top에 있는 인덱스 정보를 현재 탐색 중인 인덱스와 비교한다. 큐의 top에 있는 인덱스 정보와 현재 탐.. 2020. 11. 29. 이전 1 ··· 4 5 6 7 8 9 10 다음
