Leetcode : Subsets
Subsets I Given an integer array nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Example 1: Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2: Input: nums = [0] Output: [[],[0]] 중복이 없는 array의 모든 부분집합을 구하는 문제이다. 아래에 소개한 방법처럼 recursive하게 풀 수도 있겠으나, 배열에 중복이 없으므로 각 원소는 각 부분집합에 속하는가/속하지 않는가의 두 가지 가능성밖에 없고, 결론적으로 ..
Leetcode: Kth largest element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1: Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2: Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 소팅되지 않은 배열에서 k번째로 큰 수를 찾는 문제이다. 가장 쉽게 떠오르는 방법은 배열을 소팅해서 끝에서 k번째 element를 찾는 것이다. 길이 N짜리 배열을 소팅하므로 time complexity는 O(nlogn)이다. class Solution: def f..
Programmers: 주식 가격
문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 prices return [1, 2, 3, 2, 3][4, 3, 1, 1, 0] 스택을 이용하는 문제이다. 가격이 오르는동안은 stack에 인덱스와 가격을 push하고, 이전보다 가격이 내려간 경우, 해당 가격보다 높은 가격이 나올 때까지 stack에서 pop해서 기간을 입력하는 방식이다. 결과적으로 stack은 증가하는 monotone stack이 된다. 마지막까지 stack에서..
Leetcode: Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. Example 1: Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,nu..
