본문 바로가기

분류 전체보기657

[Leetcode] 127. Word Ladder 문제 : https://leetcode.com/problems/word-ladder/ 문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환시퀀스 길이를 구하라. 만일 변환 불가능하다면 0을 반환하라. 126. Word Ladder2 와 비슷하게 풀었다. 126번과 이번문제와의 차이점은 반환값이 변환시퀀스 리스트인지, 변환시퀀스 길이인지이다. ex) // input beginWord = "hit", endWord = "cog", wordList = ["hit", "hot","dot","dog","lot","log","cog"] 126번 문제와 비슷하게 BFS로 풀고, 이를 위해 먼저 그래프 .. 2022. 2. 12.
[Leetcode] 121. Best Time to Buy and Sell Stock 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ i번째 날의 주식가격이 저장된 price 배열이 주어진다. 한 번의 매수, 매도를 할 수 있을 때 얻을 수 있는 최대 이익을 구하라. 만일 이익을 얻을 수 없으면 0을 반환하라. 배열을 앞에서부터 탐색하면서 최소 가격을 저장하고 탐색 중인 주식가격과 현재까지의 최소 가격의 차이들 중 최대값이 정답이 된다. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm-python/blob/main/leetcode/easy/121.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock.py 2022. 2. 4.
[Leetcode] 454. 4Sum II 문제 : https://leetcode.com/problems/4sum-ii/ 크기가 n인 4개의 정수 배열 nums1, nums2, nums3, nums4가 있다. nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 을 만족하는 튜플(i,j,k,l)의 수를 구하라. map을 이용하여 nums1 + nums2 값을 key, 개수를 value에 저장한다. nums3 + nums4 요소들을 구하면서 map 에 -1 x (nums3 + nums4)를 key 값으로 하는 요소가 있는지 확인하고 있다면 value를 정답에 더해준다. 시간 복잡도는 O(N^2) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medi.. 2022. 2. 3.
[Leetcode] 1305. All Elements in Two Binary Search Trees 문제 : https://leetcode.com/problems/all-elements-in-two-binary-search-trees/ 두 개의 bst 트리의 루트 노드들이 입력으로 주어질 때, 두 개의 트리들이 가지는 요소들의 오름차순 정렬된 리스트를 구해라. 중위순회 로 두 개의 bst를 각각 탐색하여 정렬된 2개의 리스트를 만든다. 두 개의 리스트를 앞에서부터 탐색하면서 탐색 중인 요소들 중 작은 값을 먼저 정답 배열에 추가하는 식으로 정답 배열을 만들어나간다. 시간복잡도는 두 개의 bst의 노드 개수를 각각 N, M 이라 한다면 O(N + M). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1305.%20All%2.. 2022. 1. 26.
[Kotlin] Collection - Fold, Reduce 참고 : https://kotlinlang.org/docs/collection-aggregate.html#fold-and-reduce Fold와 Reduce는 컬렉션 요소들의 연산결과를 누적해서 다음 연산에서 사용한다. 차이점은 Reduce는 처음 연산 때 첫번째, 두번째 element를 가져와서 연산을 하는 반면, Fold는 init 인자와 첫번째 element를 가져와서 연산을 한다. val list = listOf(1, 2, 3, 4, 5) list.reduce { prev, ele -> println("$prev, $ele") (prev + ele) } // 1, 2 // 3, 3 // 6, 4 // 10, 5 list.fold(0) { prev, ele -> println("$prev, $ele.. 2022. 1. 16.
[Leetcode] 452. Minimum Number of Arrows to Burst Balloons 문제 : https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/ points 배열을 start 기준 오름차순, start가 동일한 경우 end 기준으로 오름차순 정렬한다. points 배열을 앞에서부터 탐색하면서 중복되는 범위를 저장해둔다. (let, duplicate) duplicate 범위의 start가 end 보다 작아지는 경우 정답을 +1 하고 현재 탐색중인 points 배열 원소값으로 duplicate를 갱신한다. 문제의 예제 1번 예시. points = [[10,16],[2,8],[1,6],[7,12]] [1, 6] x -> [1, 6] 갱신 (정답 + 1) [2, 8] [2, 6] [7, 12] [7, 6] -> [.. 2022. 1. 13.

티스토리툴바