문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 첫 시도에 풀었던 방법은 단순히 이중 for loop 를 순회하면서 최대값을 찾는 방법이었습니다. O(n^2) 의 시간복잡도를 가져서 당연하게도, Time Limit Exceeded 가 발생했습니다. 그 다음 고려했던 방법은 nums[i] 요소의 제한 사항이 정수라는 것에 착안하여 0 을 제외하고는 절대값이 그 이전 값보다 같거나 클 수 밖에 없다는 점이었습니다. 답안을 보기 전에는 nums[i] 가 0 일 경우에 대해서만 고려해서 0 으로 초기화 되기 전의 값을 가져가면서 비교하는 방법이 있지 않을까 라는 생각을 했었는데 결국 구현하지는 못했습니다. 이 전에 있던 최소값이 이후에 나올 음수 값과 곱해지면서 최대값이 될 수 있도록,..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 아래와 같이 O(log n) 시간 내에 해결하라는 문제가 아니었다면 return Math.min(...nums); // O(n) 와 같이 한줄에 풀 수도 있지만 log n 이라는 시간 복잡도 자체에 Binary Search 등의 알고리즘으로 풀어야 한다는 힌트가 있습니다. You must write an algorithm that runs in O(log n) time. left 와 right 를 설정하여 위의 (잘 알아보기가 힘든) 그림과 같이 nums[mid] 가 nums[left] 보다 큰 경우는 mid 가 오른쪽으로 이동해야 하므로 left 값에 기존 mid + 1 값을 넣습니다. 첫 번째 구현에서는 예외 CASE 를 많이 ..

문제 정보 Leet Code 문제 링크 난이도 : Easy 해결 방법 이전에 풀었던 문제 중 #121. Best Time to Buy and Sell Stock 을 카데인 알고리즘 (Dynamic Programming) 으로 풀었을 때와 동일한 문제였습니다. dp[i] 를 i 번째 인덱스를 가장 오른쪽 끝으로 하는 subArray 의 최대값으로 정의 후 구현하면 기존 dp[i - 1] 에 현재 값인 nums[i] 를 더하거나 혹은 nums[i] 로 subArray 를 시작하는 경우로 나눌 수 있습니다. 이렇게 풀이할 경우 nums 의 길이만큼 for loop 를 1회 수행하므로 시간복잡도는 O(n) 이 됩니다. Follow up: If you have figured out the O(n) solution..

문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 문제의 답 자체는 모든 수를 for loop 나 reduce 메소드를 가지고 모든 수의 곱을 nums[i] divide 하고 0 으로 나누는 경우는 나머지를 모두 곱해서 구할 수 있습니다. 하지만 아래와 같이 제한 사항이 있기 때문에 for loop 를 순회하면서 나눗셈을 사용하지 않아야 합니다. You must write an algorithm that runs in O(n) time and without using the division operation. loop 를 두 번 순회하면서 왼쪽과 오른쪽으로 나누어 곱한 값을 result Array 에 저장하고 나머지 값을 곱해서 반환합니다. 소스 코드 // Leet Code // ..

문제 정보 Leet Code 문제 링크 난이도 : easy 해결 방법 첫 시도에는 하나의 수 라도 중복이 될 경우 true 이기 때문에 중복을 제거할 수 있는 수단 중 Set 을 사용해 구현했습니다. 코드는 간단했지만 생각보다 속도는 빠르지 않았습니다. Discuss 탭에 있던 글을 몇 가지 확인해 보니 Set 대신 Object 로 구현할 경우 모든 nums 에 대해 순회하지 않고 중복되는 수를 만났을 때 종료하는 하기 때문에 nums 의 크기가 커질 수록 Object 가 유리함을 알 수 있습니다. 1,000 elements (Set is 7x faster): Set: 0.15ms Object: 1.02ms 10,000 elements: Set: 0.87ms Object: 0.88ms 100,000 el..

문제 정보 Leet Code 문제 링크 난이도 : easy 해결 방법 첫 시도에는 단순히 이중 for loop 를 사용하여 O(n^2) 의 시간이 걸리게 구현하니 Time Limit Exceeded 을 판정되었습니다. 두 번째 시도에서는 prices 를 두번 순회하지 않기 위해 고민을 하던 중에 변화량을 기록하는 diff 라는 Array 를 만들고 최대 부분합을 구할 수 있는 Dynamic Programming 을 사용하여 값을 구했습니다. ( 참고로, 최대 부분합을 구하는 이 알고리즘을 카데인 알고리즘이라고 한다고 합니다. 기존 DP 와 내용은 같긴한데... 자주 등장하기 때문에 그런것 같습니다. ) 이렇게 풀고 나서 Solution 탭을 확인해보니 for loop 마다 minPrice 와 maxPro..

문제 정보 Leet Code 문제 링크 난이도 : easy 해결 방법 첫 시도에는 단순히 이중 for loop 를 사용하여 O(n^2) 의 시간이 걸리게 구현을 했습니다. Follow-up 에서 아래와 같이 더 빠른 풀이법을 요구했기 때문에 다른 방식의 풀이가 필요했습니다. Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity? value 를 찾기 위해 index 를 모두 순회하여 O(n) 의 시간이 걸리는 Array 대신 맞는 key 값을 찾는데 O(1) 의 시간이 걸리는 Map 자료구조를 사용했습니다. key 는 덧셈에 사용할 숫자, value 는 index 입니다. map 에 두 개의 key 가 다 들..