본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][1673] Find the Most Competitive Subsequence 문제 : leetcode.com/problems/find-the-most-competitive-subsequence/ 부분 시퀀스들이 있을 때, 앞의 요소들부터 비교해나갔을 때, 사전 정렬과 비슷하게 가장 작은 수를 가지는 부분 시퀀스가 더 경쟁력 있다고 가정한다. ex) [1,3,4,2], [1,3,5,3]는 앞에 두 요소는 동일한 값이고 세 번째 요소는 첫 번째 배열의 요소가 더 작기 때문에 (4 < 5) 첫 번째 배열이 두 번째 배열보다 더 경쟁력있다. 정수 배열 nums, 양의 정수 k가 주어졌을 때, 크기가 n인 nums 배열의 가장 경쟁적인 부분 시퀀스를 구해라. stack을 사용한다. nums배열의 i번째 요소인 num를 stack에 추가한다고 해보자. 1. num을 stack의 적절한 위치.. 2021. 1. 21.
[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][1010] Pairs of Songs With Total Durations Divisible by 60 문제 : https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/ 시간배열 time이 주어질 때, 이들 중 서로 다른 원소 2개를 더한 값이 60으로 나누어떨어지는 pair들의 수를 구하라. 60 크기의 배열(cnts)을 만들고 0으로 초기화시킨다. 앞에서부터 time 배열을 탐색하면서 탐색 중인 배열 요소를 time이라 하자. cnts[60%time]들과 time을 pair로 하면 정답이 가능하다. ex) time = 20 이면 40, 100, 160 ... 이 가능하고 이들 횟수는 cnts[40]에 저장되어 있기 때문에 정답에 cnts[40] 값을 더한다. 그리고 cnts[60%time]에 time 횟수인 1을.. 2020. 12. 8.
[leetcode][1492] The kth Factor of n 문제 : leetcode.com/problems/the-kth-factor-of-n/ 양수 n, k가 주어질 때, n으로 나누어 떨어지는 정수들을 오름차순 정렬했을 때, k번째로 나오는 수를 구하라. 1부터 루트 n 만큼 반복문을 돌면서 k를 감소시킨다. 만약 n이 탐색 중인 수 i 으로 나누어 떨어졌을 때 배열에 n/i를 저장한다. 탐색 중에 k가 0이 된다면 i가 정답이 된다. 만약 i의 제곱이 n이라면 반복문 중에 k를 한 번 소모하는데 벌써 사용이 되었으므로 배열에 저장하지 않는다. 탐색이 끝났을 때 배열 크기보다 k가 크다면 정답이 없는 경우이므로 -1을 반환한다. 정답이 있는 경우 배열의 뒤에서 k번째에 있는 수가 정답이 된다. 시간복잡도는 O(루트n). 소스코드 : github.com/fpd.. 2020. 12. 5.
[leetcode] [239] Sliding Window Maximum 문제 : leetcode.com/problems/sliding-window-maximum/ 정수배열 nums 이 주어지고 슬라이딩 윈도우 크기 k가 주어진다. 배열의 맨 왼쪽부터 k개를 유지하면서 오른쪽으로 탐색하는 슬라이딩 윈도우가 있을 때 슬라이딩 윈도우가 오른쪽으로 한 칸 씩 이동할때마다 해당 슬라이딩 윈도우에 있는 요소들 중 가장 큰 값을 가지는 숫자를 배열에 저장해서 반환하라. 우선순위 큐에 요소들을 저장한다. 이 때, nums 요소와 인덱스를 같이 저장한다. 우선순위는 nums 요소(정수)로 판단한다. 만약 탐색 시 탐색 중인 nums 인덱스가 k이상일 때, 우선순위 큐를 탐색하면서 큐의 top에 있는 인덱스 정보를 현재 탐색 중인 인덱스와 비교한다. 큐의 top에 있는 인덱스 정보와 현재 탐.. 2020. 11. 29.

티스토리툴바