본문 바로가기

easy64

[Leetcode] 703. Kth Largest Element in a Stream 문제 : https://leetcode.com/problems/kth-largest-element-in-a-stream/ k, nums 배열을 초기값으로 입력받고, 정수값 val을 nums 배열에 추가하는 함수 add를 제공할 때, k번째로 큰 원소를 찾기위한 클래스를 설계해라. 최대힙, 최소힙을 만들고 최소 힙의 크기는 k로 유지시킨다. 최소힙에는 k개의 큰 수들이 들어갈 것이고 이외의 수들은 모두 최대힙에 넣는다. nums = [1,2,7,4,3], k = 2 로 예를 들어보자. 1, 2 원소는 min heap에 용량이 아직 남았으므로 모두 min heap 에 넣어준다. 3번째 원소 7을 넣을때는 min heap이 모두 찼으므로 min heap의 top에 있는 수와 7을 비교한다. min heap의 .. 2022. 4. 8.
[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] 1496. Path Crossing 문제 : https://leetcode.com/problems/path-crossing/ path를 탐색하며 현재 위치 좌표를 갱신한다. 갱신하면서 set에 현재 위치의 좌표에 온적있는지 확인한다. 만일 탐색한적 있다면 true를 반환한다. 탐색한적 없다면 set에 현재 위치를 추가하고 탐색을 계속한다. 모든 path를 탐색할때까지 중목된 좌표를 탐색한 적 없다면 false를 반환한다. 시간/공간복잡도는 O(N). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1496.%20Path%20Crossing.cpp 2021. 12. 28.
[Leetcode] 1103. Distribute Candies to People 문제 : https://leetcode.com/problems/distribute-candies-to-people/ candies 개의 사탕을 n명의 사람들에게 배분하려고 한다. 첫 번째 사람에게는 1개, 두 번째 사람에게는 2 ... n번째 사람에게는 n개의 사탕을 나눠준다. 이 후, 다시 첫 번째 사람에게 n+1, 두 번째 사람에게는 n+2 ... n번째 사람에게는 2n개의 사탕을 나눠준다. 이 절차를 모든 사탕을 나눠줄때까지 반복한다. 만일 나눠줄 사탕이 부족하다면 남은 사탕을 해당 사람에게 주고 해당 절차를 종료한다. 사탕을 모두 나눠줬을 때, 사람들이 가지는 사탕의 개수들의 리스트를 구하라. candies를 1, 2, 3 .. 개씩 모든 사람들에게 차례대로 모든 사탕을 소요할 때까지 나눠준다. .. 2021. 12. 21.
[Leetcode] 976. Largest Perimeter Triangle 문제 : https://leetcode.com/problems/largest-perimeter-triangle/ 정수 배열 nums가 주어질 때, 이 길이 중 3개로 면적이 0보다 큰 삼각형을 만들 때, 이들 삼각형들 중 가장 큰 둘레를 구하라. 삼각형을 만들 수 없는 경우 0을 반환하라. 면적이 0보다 큰 삼각형을 만드는 경우는, 길이가 (a c 조건을 만족할 수 없다면 다른 정수들도 해당 조건을 만족할 수 없다. 따라서, nums 배열을 정렬한 뒤, 가장 큰 정수들부터 a, b, c를 선택한 뒤 a + b > c를 만족하는 경우가 나오면 a + b + c가 정답이 된다. 시간복잡도는 O(NlogN). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/.. 2021. 12. 21.
[Leetcode] 1446. Consecutive Characters 문제 : https://leetcode.com/problems/consecutive-characters/ 이전 문자와 동일한지 체크하며 동일하면 cnt 변수를 +1, 아니면 1로 갱신하며 탐색하며 갱신된 cnt들 중 최대값이 정답이 된다. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1446.%20Consecutive%20Characters.cpp 2021. 12. 13.