sohan

막대들의 높이가 리스트로 주어질 때, 두 막대 사이의 최대 넓이를 가지게 하는 "넓이"를 구하자. 이상적인 최대 넓이는 두 막대가 가장 멀리 떨어져있으면서, 높이가 최대가 되게 하는 것이다. 가장 큰 넓이와 높이를 유지하게 하는 탐색을 투 포인터로 손쉽게 해결할 수 있는데.. 처음에 제일 양쪽 끝에서 시작하면서, 둘 중의 낮은 막대를 점점 안쪽으로 옮겨오면서 넓이를 계산하는거다. 이걸 두 막대의 포인터가 교차하는 지점까지 탐색을 한다. class Solution: def maxArea(self, height: List[int]) -> int: answer = 0 st = 0 ed = len(height)-1 while st  아이디어는 굉장히 단순한..

integer array와 subarray의 길이를 나타내는 k가 인자로 주어졌을 때, array에서 길이 k의 subarray의 최대 평균 값을 반환하자. 슬라이딩 윈도우 기법으로 모든 subarray를 순차탐색하며 최대 평균(or 합)을 계산할 수 있다. 매번 subarray의 평균을 새롭게 계산하는 것이 아니라, 이전 subarray를 캐싱을 해서 연산을 최소화할 수 있다.  class Solution {public: double findMaxAverage(vector& nums, int k) { double cur_sum = 0.0; double max_sum = 0.0; for (int i = 0; i max_sum) max..

문자열 t에서 문자들을 지웠을 때, s를 만들 수 있는지, 판단하는 문제이다. 간단하게 떠올린 아이디어는, t를 iteration하면서, s의 문자들이 순서대로 존재하는지 확인하는 것이다. t 안의 모든 문자 탐색이 끝났을 때, s의 모든 문자를 찾지 못했으면, false를 반환하도록 했다. class Solution {public: bool isSubsequence(string s, string t) { int target_idx = 0; for (int i = 0; i  굉장히 심플하다. s의 index를 저장하는 target_idx를 이용해서 t내에서 같은 문자를 발견하면, target_idx를 하나 옮겨서 다음 문자가 존재하는지 순차적으로 탐색한다. 그리고 반복이 끝..

정수 배열이 인자로 주어졌을 때, 0인 요소들은 우측 끝으로 모으고, 나머지 정수들은 순서를 그대로 유지하며 앞으로 당겨와야한다.  example 1에서 보면, 0들은 다 뒤로 밀려나고, 나머지 정수들은 "순서 그대로" 앞으로 옮겨왔다. 최적의 방법은 아니지만, 맨 앞부터 탐색하면서 0을 만나면, 가장 가까운 0이 아닌 정수를 만나면 자리를 바꿔주면서 뒤로 밀었다.  class Solution {public: void moveZeroes(vector& nums) { int left = 0; while (left 가장 바깥 while문인 left는 앞에서부터 0을 탐색한다. 그리고 안쪽의 for문은 0이 아닌 수를 탐색하며 앞으로 당겨온다.  직관적이긴한데, 제..

string이 주어질 때, 모음에 해당하는 문자들을 역으로 배치해보는 문제.   문제에 주어진 예시를 보면 뭔말인지 단번에 알 수 있다. 모음 리스트를 주어진 문자열 내에서 역순으로 다시 재배치하는 것. 가장 단순하게 생각해보면, 주어진 문자열에서 모음을 모두 찾아서 리스트를 만들고, 이를 다시 역순으로 바꿔서 문자열에 끼워넣을 수 있다. 하지만 이 방법에서 비효율적일 수 있다고 생각한 점이 (1) 문자와 해당 index를 같이 저장해야 한다는 것과 (2) two-stage라는 것이다.  결국 문제는 모음을 찾고, 거꾸로 배치만 하면 되는 건데, 주어진 문자열의 앞뒤에서 각각 모음을 탐색하며 서로 위치를 바꾸는 식으로 문제를 해결하도록 투 포인터 알고리즘을 써보기로 생각했다. class Solution..

비어있는 상태 0 또는 꽃이 있는 상태 1인 형태의 flowerbed가 주어진다. 꽃은 절대 인접한 곳이 심겨있지 않다. 이 때, 얼마나 많은 꽃을 새로 인접하지 않은 채로 심을 수 있는지, 인자로 들어온 n 이상 심을 수 있으면 true 아니면 false를 반환하는 문제이다. 모든 i번째 요소를 탐색하며 앞뒤(i-1과 i+1) 영역을 탐색하면 되는 문제이다.  이 문제에서 신경써야 할 포인트는 flowerbed가 1일 수 있다는 점과 맨 앞과 맨 뒤의 요소를 어떻게 간결하게 처리할 것인가?이다. 맨 앞이거나 맨 뒤의 경우, 앞이나 뒤의 요소가 존재하지 않는다. 이때, index가 존재하지 않는 곳은 사실상 empty 상태인거나 마찬가지이므로 이를 0으로 처리해주면, 복잡한 조건식을 세울 필요 없이 문제..

얘도 easy peasy 문제입니다. n개로 정수로 이루어진 배열이 주어집니다. 여기에 각 kid가 extraCandies를 가졌을 때, 해당 kid가 주어진 배열 내에서 가장 큰 수를 가지는지? 판단하는 문제입니다. 배열을 활용해보는 기본적인 문제입니다.  1. 제출 코드class Solution {public: vector kidsWithCandies(vector& candies, int extraCandies) { vector result; int cur_max = *max_element(candies.begin(), candies.end()); for (int i = 0; i = cur_max){ result.push_back(..

두 개의 string이 주어졌을 때, 두 개를 교차하며 합치는 문제. 두 문자열의 길이가 같을 수도, 하나가 더 길 수도 있음을 처리해야 한다.  1. 교차하며 더하기string result = "";int loop_num = min(word1.length(), word2.length());for (int i = 0; i 두 문자열의 길이 중 최소값을 구해서 교차하며 더할 횟수를 정의할 수 있다.   2. 길이가 다른 부분 처리하기if (word1.length()==word2.length()) return result;if (word1.length() 만약 길이가 같다면, 합쳐진 문자열을 반환하고, 그렇지 않다면 남은 뒷부분을 이어 붙여준다. substr 함수를 사용하면 4ms, 사용하지 않는 위 ..