Algorithm/LeetCode5 [LeetCode][C++/Python] 238번: Product of Array Except Self (262) 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 문제를 보자마자 든 생각은 전체 수를 다 곱한다음, 해당 자리의 수로 나누는 방식이다. 아마 나같은 일반인이라면 당연히 나누는 방식을 생각했을 것 이다... 하지만 문제 제약 조거을 보면.... "나누기 금지".... 따라서 좀더 생각을 하게 되었다. 일단 문제는 O(N)안에 해결 가능해야 한다는 점이다. 일단 투포인터 비슷한 방식으로 해야 하지 않을까? 란 생각이 먼저 들었다. O(N)안에 가능해야 하니 말이다! 어떤 수 하나를 생각해보면, 그 수의 index의 양옆 => (0 ~ index - 1), (index + 1 ~ N)의 수를 전부 곱해야 한다. 그럼 우선 배열을 순회하면서 왼쪽의 곱들만 구하고.. Algorithm/LeetCode 2023. 1. 18. [LeetCode][C++/Python] 42번: Trapping Rain Water (261) 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 1. Stack을 활용한 풀이 처음 떠오른 방식은 Stack을 사용하는 방식이었다. (뭔가 예전에 풀어본건가? 그냥 보자마자 Stack부터 떠올랐다) Stack에 게속 index를 추가하면서, 현재를 기점으로 이전보다 높이가 더 높은 경우에 해당 volume을 계산하여 결과변수에 더해준다. 글만 보면 이해가 안갈 수 있다, 다음 그림을 살펴보자. 우선 맨처음 1번 블록을 보면, 인덱스 2에서 3으로 넘어갈때 이전보다 높이가 높아지는 곳 이다. (0에서 2로) 따라서 다음 while문의 height[i] > height[stack.top()]을 만족시키게 된다. while (!height_stack.empty() .. Algorithm/LeetCode 2023. 1. 5. [LeetCode][C++/Python] 5번: Longest Palindromic Substring (260) 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 2가지 접근 방법이 있다. 사실 문제를 보면 바로 떠오르는 내용은 일반적으로 DP와 LCS(Longest Common Substring)이다. 따라서 나는 1) DP로 문제를 해결하려 노력하였다. 문제를 풀고 나니 보고 있는 책 에서는 2) 투포인터를 활용한 슬라이딩 윈도우 방식을 사용하였다. 이 방식 또한 정리해볼까 한다. 1) DP방식 접근 우선 DP로 푸는 경우 DP[i][j]의 의미를 i번째 부터 j까지가 palindrome인 경우 True를 대입하도록 하였다. 따라서 재귀적으로 DP[i][j]이 palindrome이려면 DP[i+1][j-1]이 palindrome 이여야 하고, 또한 str[.. Algorithm/LeetCode 2022. 12. 29. [LeetCode][C++/Python] 49번: Group Anagrams (259) 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 문자열의 원소순으로 정렬을 하면 같은 anagram의 원소들은 같은 문자열을 갖게 된다. 이점을 이용하자. 예를 들어 다음과 같은 3개의 예시의 경우 "ate","eat","tea" 문자순으로 정렬하면 모두 "aet" 값을 갖게 된다. 이를 Map 자료형을 이용하여 처리하면 된다. 나의 코드 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 1. C++ using namespace std; class Solution { public: vector groupAnagrams(vector& strs) { unordered_map word_map; for (auto word : strs) .. Algorithm/LeetCode 2022. 12. 28. [LeetCode][C++/Python] 937번: Reorder Data in Log Files (258) 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 크게 생각할 문제라기 보다는, 정렬 조건을 어떻게 잘 적용시키는지가 중요한 문제이다. C++, Python 둘다 람다를 활용하여 간편하게 정렬 조건을 전달해줄 수 있다. 이를 활용해보자! 나의 코드 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 1. C++ using namespace std; class Solution { public: vector reorderLogFiles(vector& logs) { vector digits; vector letters; for (auto log : logs) { const vector &results = split(log, " ");.. Algorithm/LeetCode 2022. 12. 26. 이전 1 다음
