알고리즘 문제/Leetcode283 [Leetcode] 668. Kth Smallest Number in Multiplication Table 문제 : https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ m x n 크기의 2차원 배열(1-indexed)이 있다. 배열 값은 각 요소들의 행, 열 인덱스의 곱이다. m, n, k가 주어졌을 때, m x n 2차원 배열에서 k 번째로 작은 요소 값을 구해라. k 번째로 작은 요소 값은 완탐을 하지 않는 이상 구하기 어렵기 때문에, 정수 x 보다 작은 요소 값들이 몇 개인지 구해보자. m = 3, n = 3, k = 4을 예로 들어보자. 1 2 3 2 4 6 3 6 9 1 2 2 3 3 4 6 6 9 구하고자 하는 문제를 좀 더 분해해서 각 행에서 정수 x 보다 작은 요소 값들이 몇 개(let, cnt)인지를 먼저 구해보.. 2021. 11. 16. [Leetcode] 80. Remove Duplicates from Sorted Array II 문제 : https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ 앞에서부터 탐색하면서 연속으로 등장하는 정수의 수를 저장한다. 만일 이전과 같은 정수인데 3개 이상 등장하는 수라면 해당 요소를 삭제한다. 리턴값은 삭제하고 난 뒤의 nums 배열의 사이즈를 반환한다. 시간복잡도는 O(N). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/80.%20Remove%20Duplicates%20from%20Sorted%20Array%20II.cpp 2021. 11. 15. [Leetcode] 34. Find First and Last Position of Element in Sorted Array 문제 : https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ 내림차순 정렬된 정수 배열과 target 값이 주어지면 배열에서 target 값의 시작 위치와 끝 위치를 찾아라. 만일 target을 찾을 수 없다면 [-1, -1]을 반환해라. O(log N) 복잡성을 가지는 알고리즘을 작성해라. logN 복잡성이라는거 보니 이분탐색으로 해야겠다. 이분탐색을 진행하면서 target 값을 찾는 경우 정답배열의 최소값, 최대값을 갱신한다. 그리고 시작 위치와 끝 위치를 찾아야 하므로 여기서 끝내지 않고 (left, m-1), (m+1, right) 로 이분탐색 2개를 다시 실행시킨다. (m = (left + r.. 2021. 11. 14. [Leetcode] 739. Daily Temperatures 문제 : https://leetcode.com/problems/daily-temperatures/ 일별 온도 정수 배열이 주어지면 해당 날짜에서 볓 번째 날이 지났을 때 해당 날짜의 온도보다 더 높은 온도를 얻을 수 있는지 저장한 배열을 구하라. 만일 가능한 날이 없다면 0을 저장해라. 배열을 뒤에서부터 탐색하면서 stack에 탐색하는 일자의 온도보다 높은 온도만 존재하게 유지한다. 탐색하면서 만일 stack에 탐색 일자의 온도보다 높은 온도가 존재하지 않는다면 0, 존재한다면 stack의 top에 있는 온도의 인덱스에 현재 인덱스를 뺀 값을 정답 배열에 저장한다. Ex) temperatures = [73,74,75,71,69,72,76,73] 시간복잡도는 O(N) 소스코드 C++ : https://gi.. 2021. 11. 13. [Leetcode] 203. Remove Linked List Elements 문제 : https://leetcode.com/problems/remove-linked-list-elements/ 링크드 리스트의 헤드와 정수값 val 이 주어지면 링크드 리스트들 중 노드 값이 val 과 같은 노드들은 제거한 뒤 헤드를 반환하라. head 부터 탐색하면서 만일 탐색 중인 노드 값이 val이 아니라면 다음 노드를 탐색한다. 만일 삭제해야 하는 노드라면 탐색 중인 노드의 바로 전 노드에 탐색 중인 노드의 next 노드를 연결한다. 이를 위해 최근에 탐색한 노드를 별도의 변수에 저장하고 있어야 한다. 만일 삭제될 노드가 head 노드라면 탐색중인 노드의 next 노드를 새로운 head 노드로 세팅한다. 시간복잡도는 O(N). N = 링크드 리스트 노드 개수. 소스코드 : https://git.. 2021. 11. 13. [Leetcode] 1413. Minimum Value to Get Positive Step by Step Sum 문제 : https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/ 정수형 배열 nums가 주어질 때, nums 정수들을 처음부터 하나씩 수를 더해나갈 때 단계별 더하는 수가 항상 양수가 되도록 하는 최소 초기값 양수 startValue를 구하라. nums 배열을 앞에서부터 탐색하면서 부분합을 구한다. 구한 부분합들 중 최소값을 구해서 (최소값 x -1) + 1 한 값이 정답이 되는데 정답은 양수여야 하므로 만일 이 값이 양수가 아니라면 1을 반환한다. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1413.%20Minimum%20Value%20t.. 2021. 11. 11. 이전 1 ··· 12 13 14 15 16 17 18 ··· 48 다음
