LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length

초기 접근 방법 ❗️처음에 생각한 방향 for문으로 string의 길이만큼 다 돌면서 주어진 길이 k만큼씩 반복해서 일일이 찾을 생각 하지만 시간 복잡도가 O(n*n)인 것을 알기 때문에 좋지 않은 알고리즘이라고 생각함 코드 자체는 금방 짜기 때문에 일단 Brute Force로 되나 해보기나 하자라는 마음으로 아래와 같이 구현 Brute Force bool isVowel(char s){ switch(s){ case 'a': case 'e': case 'i': case 'o': case 'u': return true; default: return false; } } int maxVowels(char * s, int k){ int len = strlen(s); int max = 0, temp = 0; for..

• format_list_bulleted Algorithm/LeetCode
• · 2023. 8. 13.
• textsms

LeetCode 643. Maximum Average Subarray I

초기 접근 방법 ❗️처음에 생각한 방향 처음부터 해당 알고리즘을 공부할 목적으로 Sliding Window가 뭔지 검색하고 풀음 최종 접근 ✅ 고정된 크기 k만큼의 avg를 먼저 구하고 해당 avg와 sliding 해서 구할 새로운 avg와 비교 ✅ Sliding 한다는 것 : window에 포함될 새로운 배열만큼 더하고, window에서 빠질 가장 작은 배열만큼 뺀다. for문 안에서 주어진 변수로 어떻게 한 번에 다 표시할 수 있을까 고민했고, 주어진 k와 i를 이용해 모두 표현 가능 >> [i]번째는 더하고, [i-k] 번째는 빼지는 구조 구현 Runtime : 129ms Beats 89.49% of users with C double findMaxAverage(int* nums, int numsS..

• format_list_bulleted Algorithm/LeetCode
• · 2023. 8. 13.
• textsms

LeetCode 11. Container With Most Water

⭐️ 이 문제 다시 풀어보기 ⭐️ 초기 접근 방법 ❗️처음에 생각한 방향 두 높이 사이의 차이를 하나의 변수에 두고, 반복문을 돌면 해당 변수와 다른 높이 사이의 차이 크기를 비교 더 높이 차이가 적은 것이 있으면 넓이 계산해보고 현재 max인 넓이와 비교하기 ❌ 코드로 구현하다가 실패 예외사항이 너무 많고, 신경써야할 부분이 너무 많음 최종 접근 ✅ 넓이를 결정할 높이는 두 height 중에 더 짧은 길이로 결정됨 따라서, (b-a)*min(a,b) 가 최종 넓이 ✅ 가로 길이와 높이를 모두 다 알아야하고, 가로 길이는 뺄셈 연산을 통해 구해야하기 때문에 맨 앞부터 시작하는 Left pointer, 맨 뒤부터 시작하는 Right pointer 를 두고 계산 ✅ 반복문 탈출 조건은? Left Pointe..

• format_list_bulleted Algorithm/LeetCode
• · 2023. 8. 13.
• textsms

LeetCode 334. Increasing Triplet Subsequence

⭐️ 다시 풀어보기 ⭐️ 초기 접근 방법 ❗️처음에 생각한 방향 더 큰 수를 구하기 위해 두 수의 차이를 이용하는 게 어떨까? a-b > 0 이면 a가 더 큰 것이다라는 개념을 이용해보자. Brute Force bool increasingTriplet(int* nums, int numsSize){ for(int i=0; i

• format_list_bulleted Algorithm/LeetCode
• · 2023. 8. 13.
• textsms

LeetCode 724. Find Pivot Index

초기 접근 방법 ❗️처음에 생각한 방향 pivot index를 기준으로 for문을 돌려서 각각 left sum과 right sum을 비교하려고 함 - left의 경우, 감소하는 방향으로 더하고 - right의 경우, 증가하는 방향으로 더해 - 마지막에 최종 비교했을 때 두 값이 값으면 pivot index를 return함 ✅ 기준이 있는 경우, 오른쪽과 왼쪽을 나눌 생각하기로 했기 때문에 (아래 문제 Take away) https://brynn-park.tistory.com/16 이 경우는 예외처리를 따로 해주지 않아도 된다는 장점이 있음 맨 앞과 맨 뒤가 pivot인 경우도 다 포함해서 코드를 구현 다만 시간 복잡도 부분에서 아무래도 O(n*n)이기 때문에 느리다는 단점이 있어서 조금 더 간단하게 구현..

• format_list_bulleted Algorithm/LeetCode
• · 2023. 8. 11.
• textsms

LeetCode 1732. Find the Highest Altitude

초기 접근 방법❗️처음에 생각한 방향 실제 고도를 구하기 위해 gainSize보다 1만큼 큰 altitude array를 따로 만들고 해당 array안에서 MAX 찾는 코드로 구현하자 Brute Forceint largestAltitude(int* gain, int gainSize){ int* altitude = (int*) malloc((gainSize+1)*sizeof(int)); altitude[0] = 0; int max = altitude[0]; for(int i=1; i

• format_list_bulleted Algorithm/LeetCode
• · 2023. 8. 11.
• textsms