문제: Best Time to Buy and Sell Stock 관련 토픽: Array, Dynamic Programming난이도: Easy 링크 https://leetcode.com/problems/best-time-to-buy-and-sell-stock요구사항prices 배열은 i번째 날짜의 주식의 가격을 담음정해진 하루에 주식을 사고, 주식을 산 시점 이후에 주식을 판매주식을 구매, 판매하며 어떤 조합이 가장 큰 수익을 낼 수 있는지 탐색수익이 발생하지 않는 경우에는 0을 반환  조건1 10만개의 요소를 다루는 문제는 효율적으로 풀이 하는 것이 좋다 O(n) ~ O(nlogn) 시간 복잡도의 풀이가 필요! 0 최대값,최소값을 구할 때 값 초기화의 기준으로 사용 가능풀이 문제 태그에는 Dynamic ..

문제 링크 https://leetcode.com/problems/top-k-frequent-elements/description/ Intuition 주어진 array에서 가장 중복이 많은 k개의 element를 결과값으로 반환 그렇다면 정렬하고, 중복을 찾기 위해선 hash를 써야겠군 Approach hash를 쓰기 위해서는 python의 dictionary를 사용 가장 많이 중복되는 element 별로 저장된 dictionary를 그 후에 정렬! 정렬된 중복_숫자_맵 에서 k개의 key값을 반환 dict에서 get()함수는 parameter가 2개! 두번째 param은 optional로 조회하는 key 값이 없는 경우에 반환할 값을 설정 numMap[num] = numMap.get(num,0) → nu..

문제 링크 https://leetcode.com/problems/two-sum/description/ Intuition 주어진 array의 element 중에 target 값으로 합의 수가 맞는 조합을 찾아야 하면..모든 element를 합해서 확인해 보자 first + second index element의 합을 확인하고 넘어가야 한다 Approach 당장 생각나는건...outer loop에서는 index 0 부터 좌항에 들어가는 인자를 iterate하고 inner loop에서는 우항에 들어가는 인자를 iterate 해서 둘의 합을 확인하는 방법 Complexity Time complexity: O(N^2) Space complexity: Code class Solution: def twoSum(sel..

Intuition Anagram은 주어진 문자열의 character를 재배치 했을 때에도 다 같은 구성의 character를 가지는 단어 혹은 문구를 뜻한다고 한다. 그러니 길이가 같아야지? 같은 구성의 character를 가져야하겠네? Approach 같은 구성의 문자를 가진것을 어떻게 비교하면 좋지? 정렬한 후에 같은지 확인하면 효율적이지 않을까 길이가 다른 경우는 먼저 False를 반환 하는게 좋을 것 같다 Complexity Time complexity: O(nlogn) 평균 / W.C (= worst case) 이유는 python의 sorted() 함수는 Timesort라는 정렬 알고리즘을 사용 Timesort 알고리즘이란? insertion sort 와 merge sort의 장점만을 합쳐서 만..

Intuition python 으로 문제 풀이를 하기로 했으니 counter 함수를 사용해서 풀이하면 될것같다! Approach counter 함수로 첫번째 풀이를 했는데, time limit exceeded 가 떴음 두번째 제출에서는 set 자료구조를 사용해서 풀이 set은 중복을 허용 X 주어진 data set을 set에 넣으면 중복이 사라져서 전체 사이즈가 달라짐 set의 사이즈와 nums의 사이즈를 비교! Complexity Time complexity: first attempt: O(N^2) list.count() 함수는 내부적으로 모든 PyObject를 iterate 하고, 주어진 입력값과 compare 하기 때문에 O(N) complexity를 가진다 참고: https://stackoverf..