본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][1675] Minimize Deviation in Array 문제 : leetcode.com/problems/minimize-deviation-in-array/ n개의 양의 정수를 가지는 배열이 주어진다. 수가 짝수이면 2로 나눌 수 있고 홀수면 2를 곱할 수 있다. (복수번 적용 가능) 배열의 편차는 두가지 요소의 차이 중 최대 값이다. 구할 수 있는 배열의 편차 중 최소 값을 구하여라. 짝수면 감소. 홀수면 증가시킬 수 있다. 짝수를 2로 나누면 짝수 혹은 홀수가 나온다. 하지만 홀수를 2로 곱하면 반드시 짝수가 된다. 즉, 모든 요소들의 최대값들은 그 자신의 수(짝수인 경우)거나 x2한 수(홀수인 경우)이다. 따라서 모든 수들을 먼저 최대값으로 만든 뒤, 최대값을 감소시키면서 배열의 편차의 최소 값을 구한다. 구현은 set을 이용했고, 최대 최소는 set의 .. 2021. 1. 31.
[leetcode][987] Vertical Order Traversal of a Binary Tree 문제 : leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/ 이진 트리 노드의 루트 노드가 주어진다. 루트 노드는 (0, 0) (x,y) 위치를 가지고 왼쪽 자식 노드, 오른쪽 자식 노드로 갈수록 (x-1, y-1), (x+1, y-1) 위치 값을 가진다. 동일한 x 좌표 값을 가지는 노드들의 val 값의 배열을 x 좌표의 오름차순 정렬하여 구하라. 만일 동일한 x 좌표 값을 가진다면 y 좌표의 오름차순 정렬된 배열을 가진다. y좌표도 동일하다면 노드의 val 값을 오름차순 정렬한다. dfs로 풀 수 있다. 루트노드로부터 왼쪽, 오른쪽 자식으로 탐색하면서 (x-1, y-1), (x+1, y-1)로 좌표 값을 갱신시킨다. x 좌표를 키값, (.. 2021. 1. 30.
[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][1657] Determine if Two Strings Are Close 문제 : leetcode.com/problems/determine-if-two-strings-are-close/ 1. 문자열에서 어떤 두 문자의 위치를 바꾼다. ex) abcde -> aecdb (b, e 교환) 2. 문자열에 존재하는 두 문자들을 모두 바꾼다. ex) aacabb -> bbcbaa (a, b 교환) word1 문자열에 위 두 연산을 해서 word2 문자열을 만들 수 있는지 구하라. word1 문자열을 앞에서부터 탐색하면서 두 연산을 실행시켜가면서 word2 문자열을 구해봐야하나 싶지만 더 간단한 방법이 있다. 1번 연산은 문자열의 문자 위치는 변경가능하므로 위치는 무의미하다는 것을 의미한다. 즉, word1, word2의 문자들의 개수(a의 개수, b의 개수 ... )만 맞출 수 있다면.. 2021. 1. 22.
[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.

티스토리툴바