Identifying the Problem

이진트리를 순회하면서, 가장 큰 path sum을 구한다.

단, 노드는 최대 한번만 path에 나타나야한다.

Input: root = [-10,9,20,null,null,15,7]

Output: 42

Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Organizing thoughts

tree를 중위 순회하면서, 합을 누적시키다가, 합이 음수가 되면,

sum을 다시 0으로 초기화하고 최대값을 구해 나간다.

하지만 이렇게 쉽게 풀리면 hard가 아니라 easy이다.

작성한 코드를 제출했지만 내가 생각한 답과 달랐다.

Mistake

path의 개념을 잘못 이해했다.

하나의 선이 있다면 그 선이 노드에 한번만 걸쳐가게 해야하는데,

그 선이 노드를 두번 걸치게 되는 줄 알았다.

중위 탐색의 순서를 배열로 생각했을 때 가장 큰 max subarray를 구하는 문제로 착각했던 것이다.

Sourcecode

## 내가 짠 코드

class Solution {
    int sum = 0;
public:
    int maxPathSum(TreeNode* root) 
    {

        
        if(!root) return 0;
        
        maxPathSum(root->left);
        sum+=root->val;
        cout<< sum << '\n';
        if(sum < 0) sum  = 0;
        maxPathSum(root->right);
        
        return sum;
    }
};

## 정답 코드 및 출처

이 곳에서 각 tree 별 case를 확인 할 수 있다.

class Solution {
    int sum;
public:
    int maxPathSum(TreeNode* root) 
    {

        sum = INT_MIN; //적어도 최소 하나는 더해야 하기에 
        			   //0이 아닌, 가장 작은 int값을 최소값으로 설정
        help(root);
        return sum;
    }
    
    int help(TreeNode* root)
    {
        if(!root) return 0; //재귀 탈출
        
        int left = max(0,help(root->left)); //case 2
        int right = max(0,help(root->right)); //case 3
        
        sum = max(sum , left + right + root->val); 
        //case 1 : root와 left,right가 기존 sum 보다 크다면 셋의 합을 sum으로 한다.
        
        return max(left,right) + root->val;  
        //case 4 left, right가 음수면, left와 right를 정하는 과정에서 l,r을 버린다. 
    }
};

Identifying the Problem

모든 이진트리를 뒤집는다.

Organizing thoughts

Sourcecode

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(!root) return NULL; //탈출 조건
        
        swap(root->left, root->right); //왼쪽과 오른쪽 node를 뒤집음
        
        invertTree(root->left); //재귀 탐색
        invertTree(root->right);
            
        return root;
    }
};

Identifying the Problem

이진트리의 최대 깊이를 구한다.

Organizing thoughts

정답 참고 출처

tree의 속성인 재귀를 활용해 트리의 깊이를 들어갈 때마다, 

1을 누적해서 더하고, 왼쪽과 오른쪽의 트리의 깊이를 비교하며

최대를 구한다.

Sourcecode

class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        return root ? 1 + max(maxDepth(root->left), maxDepth(root->right)): 0;
    }
};

Identifying the Problem

string 문자열에서 가능한 모든 palindromic substrings의 개수를 구한다.

Organizing thoughts

전체적인 아이디어는 5번 문제와 유사하고, dp가 true인 경우의 개수를 센다고 보면 된다.

하나의 차이점을 두자면, 이번 문제는 window slicing으로 window의 개수를 늘려가며 탐색하였다.

Sourcecode

class Solution {
public:
    int countSubstrings(string s) 
    {
        int m = s.size();
        vector<vector<int>> dp(m , vector(m,0));
        int ans = 0;
        
        for(int i = 0; i<m; i++)
        {
            dp[i][i] = 1;
            ans++;
        }
        
        for(int w = 1; w<m; w++)
        {
            for(int k = 0; k<m-w; k++)
            {
                if( ( (dp[k+1][w+k-1] == 1 || w==1  )&& s[k] == s[w+k]) ) 
                //window의 size가 1 이거나, 이전 값이 true 인 경우
                //양 끝이 동일한 문자면 해당 substring은 Palindromic 이다.
                {    
                  dp[k][w+k] = 1;
                  ans++;
                }
            }
        }

        return ans;
    } 
    
    
};

Identifying the Problem

string 문자열 내에서 가장 긴 Palindromic(좌우 대칭)인 문자열을 구한다.

Organizing thoughts

#1은 내가 생각한 풀이 , #2는 다른 사람의 코드를 해설하였다.

#1 window slicing으로 window 크기를 s.size 에서 점점 줄여나가면서 판단한다.

window에 해당하는 string과 뒤집은 string이 동일한지 판단한다.
reverse 사용 한다면 O(n²)로 보이겠지만, 실제로는 O(n³)이다.

#2 가능한 모든 substring을 확인하고, 가장 긴 substing을 찾기
양파 까는 것처럼 양끝이 같으면, 그 안쪽도 같은지, 그 안쪽도 같으면 그 안쪽도 같은지
dp로 확인한다.

Sourcecode

## 내 풀이 (역시나 time limit이 뜬다.)

class Solution {
public:
    string longestPalindrome(string s) 
    {
        if(s.size() == 1) return s;
        int win_size = s.size();
        int i = 0;
        
        while(win_size >= 2)
        {
            i = 0;
            while(i + win_size - 1 < s.size())
            {
                string tmp = s.substr(i,win_size);
                reverse(tmp.begin(), tmp.end());

                if(tmp == s.substr(i,win_size))
                    return s.substr(i,win_size);
                i++;
            }
            win_size -=1;
        }
        return s.substr(0,1);
    }
};

## 정답 풀이 및 출처

https://leetcode.com/problems/longest-palindromic-substring/discuss/1273319/C%2B%2B-2D-dp-solution

핵심은 left와 right가 같다면, 그 안쪽도 같은지 계속 들어가는 것이다.
1. left right index가 같은 경우 palindromic 이므로 초기값 true
2. 가능한 모든 substring을 최소 단위부터 탐색한다.
3. left와 right의 index의 글자가 같은 경우 left 다음 right 이전의 문자도 동일한지 확인

ex : bab 라면 a는 1. 에서 palindromic 확인했으므로 bb 일 때 이전과 같은지 확인

ex : baab 라면 aa는 2. 에서 palindromic 확인했으므로 bb 일 때 이전과 같은지 확인
4. palindromic 인 경우 가장 긴 substring의 길이와 start 위치 저장

표를 자세히 보면 true 인 곳을 중심으로, 대각선 오른쪽 위에 정답이 있음을 확인할 수 있다.

이런 식으로 true가 가장 많이 연결된 dp를 찾으면 된다.

class Solution {
public:
    
    string longestPalindrome(string s) {
        int len = s.length();
        bool dp[len][len]; 
        
        if(s.length()==1)
            return s;
        
        int start = 0; int long_len = 1;
        
        for(int i=0; i<s.length(); i++)
            dp[i][i] = 1;
        
        for(int i = len-1; i>=0; i--)
        {
            for(int dist = 1; dist<len-i; dist++)
            {
                int j = dist + i;
                dp[i][j]= (dist==1)? s[i]==s[j] : (s[i]==s[j] && dp[i+1][j-1]);
                if(dp[i][j] && j-i+1 >long_len)
                {    
                    long_len = j-i+1;
                    start = i;
                }
            }
        }
        return s.substr(start, long_len);
    }
};

Identifying the Problem

두개의 문자열에서 공통된 가장 긴 문자열 길이를 구한다.

Input: text1 = "abcde", text2 = "ace" Output: 3

Explanation: 가장 긴 공통 하위 문자열은 "ace" 이므로 3을 리턴한다.

Organizing thoughts

가장 먼저 떠오른 아이디어는 긴 문자열의 기준으로 작은 문자열의 문자와 비교하며 길이를 구하는 방법이다.

하지만 이 방법은 O(n^2) 이므로 O(n)인 방법을 생각해보았다.

string관련 무네를 풀 때는, map/ dp 선에서 다 풀리기에 map으로 풀어보았다.

1. text1 과 text2의 lettermap을 만든다
2. lettermap을 비교하며 둘 중에 작은 값을 누적시킨다.ex) text1_map[‘a’] = 3 , text2_map[‘a’] = 1 이면 sum에 1을 누적
3. sum 리턴
실수 : 내가 문제를 제대로 이해하지 못했다.
text1 이 abc , text2 가 cba 라면 리턴값은 3이 아니라, 1이 되어야 한다.
즉 문자의 개수만 같아서 되는 것이 아니라, 문자의 순서도 같아야 한다.

하지만 내 풀이는 substring의 순서를 어겼다.

text1 : abc , text2 : cba 라면 return 값은 3이 아니라 1이 되어야 한다.

정답 풀이 / 해설
aab와 aca 비교한다 했을 때,
1) aab ac 와 2) aa aca 일 때 각각의 개수와 둘 중의 큰 값을 채택
1)aab , a 와 aa , ac 그리고 2)aa , ac 와 a , aca 일 때 각각의 개수와 둘 중의 큰 값을 채택
…. 이런 식으로 dp를 쌓아 올린다.
즉 처음 떠오르는 접근법대로 하면 된다.

Sourcecode

## 내 풀이

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        if(text1.size() == 0 || text2.size() == 0) return 0;
        
        int sum = 0;
        
        vector<int> map1(26,0);
        vector<int> map2(26,0);
        
        for(int i = 0; i<text1.size();i++)
            map1[text1[i] - 'a'] += 1;

        for(int i = 0; i<text2.size();i++)
            map2[text2[i] - 'a'] += 1;
        
        for(int i = 0; i<26; i++)
            sum += min(map1[i],map2[i]);
        
        return sum;
    }
};

## 정담 풀이 및 출처

중간에 있는 for문은 다음의 표를 보면 이해하기 쉽다.

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        
        int n = text1.size();
        int m = text2.size();
        
        if(n == 0 || m == 0)
            return 0;
        
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); //2차원 dp vector선언
        // 아무것도 없는 것과 비교하는 것은 0이므로 초기값을 0으로 설정
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(text1[i-1] == text2[j-1]) 
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        
        return dp[n][m];
    }
};

New things learned

dp의 목적은 가능한 모든 경우를 파악해 결과를 도출하는 것이다.
이전의 결과들의 조금의 변화가 생겨서 다음의 결과가 가능하면해당하는 모든 이전의 값들을 사용해 다음 dp를 구한다.
위 예시에서 aab와 aca를 비교하려면 aab, ac 와 aa, aca의 값을 이용하는 것 처럼 말이다.

Identifying the Problem

strs 에서 anagram 인 단어들을 묶어 리턴한다.

Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Organizing thoughts

지난 번 anagram의 lettermap을 참고하면 쉽게 풀 수 있을 거라 생각했다.

1. strs의 모든 단어의 lettermap을 추출

2. strs size 만큼 반복하며 동일한 lettermap일 경우 단어를 묶는다.

3. 단, 탐색하는 단어와 비교하는 단어가 같은 경우,

   비교하는 단어는 중복을 방지하기 위해 해당 단어의 index를 flag를 세워 탐색을 건너뛴다. 

Sourcecode

## 직접 작성한 코드 

짧은 example에서는 제대로 작동하지만, Time Limit Exceeded 발생

시간복잡도가 O(n)가 되어야한다. 

#include <algorithm>

template <class T>
static bool compareVectors(std::vector<T> a, std::vector<T> b)
{
   if (a.size() != b.size())
   {
      return false;
   }
   ::std::sort(a.begin(), a.end());
   ::std::sort(b.begin(), b.end());
   return (a == b);
}

class Solution {
public:
    
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {

    vector<vector<string>> ans;
    vector < vector <int> > lettermap(strs.size(),vector <int>(26,0));

    vector<int> flag(strs.size() , 0);
    
    int ans_c = 0; //동일 단어의 그룹 index
        
    for(int i = 0; i<strs.size(); i++) //lettermap 을 작성
        for(int k = 0; k<strs[i].size(); k++)
            lettermap[i][strs[i][k] - 'a'] +=1;
        
    for(int i = 0; i<strs.size(); i++) //탐색단어과 비교단어가 같은 지
    {
        if(flag[i] == 0)
        {
            ans.push_back(vector<string> ()); //ans 벡터의 행을 하나 추가한다.
            
            if(i == strs.size() - 1) 
            //마지막 단어의 경우 중복되었는지 아닌지만 판단하면 된다.
            //중복이 아닌 경우 단일 그룹에 추가
                ans[ans_c].push_back(strs[i]);
            
            else
            {   
                ans[ans_c].push_back(strs[i]); //탐색 단어를 그룹의 처음에 넣고 시작
                for(int k = i+1; k<strs.size(); k++)
                    if(lettermap[i] == lettermap[k]) //두 lettermap 벡터가 같다면,
                    {
                        ans[ans_c].push_back(strs[k]); //동일 단어그룹에 추가한다.
                        flag[k] = 1; //중복 방지 flag
                    }
            }
          
          ans_c +=1; //그룹 변경
        }
    }
    
    return ans; 
    }
    
    
};

##정답 코드 및 출처

정답 코드는 lettermap간의 비교가 아닌, 단어를 오름차순 정렬한 상태를 map에 집어 넣었다.

아직 hashmap과 map에 대해 잘 모르는 상태라 더 공부해보아야겠다.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        
        for (string s : strs) {
            string t = s;
            sort(t.begin(), t.end());
            mp[t].push_back(s);
        }
        vector<vector<string>> anagrams;
        for (auto p : mp) { 
            anagrams.push_back(p.second);
        }
        return anagrams;
    }
};

Mistake

2차원 벡터를 선언하고, ans.push_back(vector<string> ()); 로 하나의 행을 만들어줘야 값을 집어 넣을 수 있다.

New things learned

• 2차원 벡터 선언 방식

Identifying the Problem

interval 내에 겹치는 부분을 제거하되, 제거하는 수를 최소화하고, 제거된 interval의 수를 리턴한다.

Organizing thoughts

규칙

1. 너무 많은 범위를 잡아버리면 지울 것이 늘어난다.

2. 지우는 개수 최대 size - 1 개다.

3. interval[i][0]의 중복이 되면 안 된다.

ex : [1,2] [1,3] 이면 1이 중복이므로 하나만 남겨야 된다.

   3-1 : 하나만 남겨야 하는데 어떤 걸 남기냐면

   규칙 1을 생각했을 때, [1,3] 을 지우는 것이 옳다.

   안 겹치는 것이 중요하지, 범위를 최대화하란 말은 아니다.

   3-2 : 하나만 남겼을 때, 남은 하나가 다음 interval과 겹치면 이것도 지운다.

   ex : [2,6] [3,4] [4,5] [5,6]에서 [2,6]이 [3,4] [4,5] [5,6]과 곂치므로 [2,6]만 지운다.

Sourcecode

##직접 작성한 코드

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) 
    {
        sort(begin(intervals), end(intervals));
        
        int count = 0;
        int end = intervals[0][1];
        
        for(int i = 1; i<intervals.size(); i++)
        {
            if(intervals[i-1][0] == intervals[i][0]) //start가 같은 경우
            {count ++;  }
            else //start가 다른 경우
            {
                if(end > intervals[i][0]) //남은 하나와 겹치는 경우
                {count++; }
                else end = intervals[i][1]; //end 재설정
            }
        }
        return count;
    }
};

###정답 코드 / 출처

내 코드와의 차이점 : start가 같은 경우와 겹치는 경우를 하나로 묶어 조건을 간결하게 추렸다.

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int i = 1; //interval 의 index
        int c = 0; //count
        while(i<intervals.size()){
            if(intervals[i][0]<intervals[i-1][1]) //i-1과 i가 곂치면
            { 
                intervals[i][1] = min(intervals[i-1][1], intervals[i][1]); //end 재설정
                c++; //제거 카운트 증가
            }
            i++;
        }
        return c;
    }
};

Mistake

직접 작성한 코드는 다음 test에서 오류가 난다.

[[-52,31],[-73,-26],[82,97],[-65,-11],[-62,-49],[95,99],[58,95],[-31,49],[66,98],[-63,2],[30,47],[-40,-26]]

end 재설정 부분을 다시 생각해보아야겠다.

Identifying the Problem

범위를 나타내는 2개의 열로 이뤄진 interval 배열에 new interval을 삽입해 바뀐 interval을 리턴한다.

Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]

Explanation: [1,3] 과 [2,5]가 겹치므로 [1,5] 로 바꾸어 준다.

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]]

Explanation: [4,8] 이 [3,5],[6,7],[8,10]와 겹쳐 [3,10] 으로 합쳐졌다..

Organizing thoughts

규칙을 최대한 찾아보았다.

1. interval과 new의 요소 개수는 짝수 개

2. output은 행의 개수를 최소화 시키는 게 아니라, 영향을 준 부분만 수정한다.

3. 더 깊이 생각해보면 영향을 안준 부분은 output에 그대로 내보내면 된다.

4. 오름차순이라는 점을 이용한다.

5. 영향을 준 부분을 output에 보내는 방법을 생각해보자

    a. new의 범위는 최대 [0, interval의 최대 보다 큰 값] 최소 [n, n+1]

    b. new의 요소가 interval 내에 들어가면 범위를 변경해야 한다.

6. new가 들어갈 곳이 아무 곳도 없는 경우

    a. new의 end 부분이 interval의 처음 값 보다 작다면, 최우선에 insert한다.

    b. new의 start 부분이 interval의 마지막 값 보다 크다면, 마지막 부분에 insert한다. 

[전체적인 flow]

<second < new_start> 일 때는 정답에 추가하다가

<new_end 가 들어갈 위치를 찾으면> new_start ~ new_end 의 범위에 맞게 정답에 추가 후

<이후> 나머지를 그대로 넣으면 된다.

Sourcecode

#직접 작성한 코드

interval의 size가 1인 경우 및 다른 특정한 경우 올바르게 작동하지 않는다.

다행히 정답 코드와 전체적인 flow는 유사했다.

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans(intervals.size()+1,2);
        int start = newInterval[0];
        int end = newInterval[1];
        int flag = 0; //new의 범위를 설정하고, 탐색하는 부분이 되면 flag를 올린다.
        
        if(end > interval[0][0])
        {
            interval.push_front(newInterval);
            return interval;
        }
        if(start > interval[interval.end()][1])
        {
            interval.push_back(newInterval);
            return interval;
        }
        int k = 0;
        for(int i=0; i<interval.size(); i++)
        {
            if(interval[i][0] <= start && start <= interval[i][1])
            {
                start = interval[i][0];
                flag = 1;
            }
            else if(start < interval[i][0])
                flag  = 1;
            
            if(flag == 0)
                ans[k++] = interval[i];
            
            if(interval[i][0] <= end && end <= interval[i][1])
            {
                end = interval[i][1];
                ans[k][0] = start;
                ans[k][1] = end;
                flag = 0;
                k++;
            }
            else if(end < interval[i][0])
            {
                ans[k][0] = start;
                ans[k][1] = end;
                flag = 0;
                k++
                ans[k] = interval[i];
            }
        }
        
        return ans;        
    }
};

# 정답 코드 및 코드 출처

class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& ints, vector<int>& ni, int i = 0) {
    vector<vector<int>> res;
    
    for (; i < ints.size() && ints[i][0] <= ni[1]; ++i) 
    {
    //i를 끝까지 탐색하되, new의 end가 가능한 범위 내에서 진행한다.
    //만약 interval[i][0]가 6인데 end 부분이 4면 범위를 벗어난 것이다.
    //즉 new가 해당하는 범위를 탐색함과 동시에 new의 이전 범위를 추가하는 작업이라 생각하면 된다.
   
        if (ints[i][1] < ni[0]) //new의 범위 이전에 interval이 있으면
            res.push_back(ints[i]); //정답 배열에 interval 추가
        else 
            //탐색 중인 interval이 new 범위 안에 들어왔다면, 
            //첫 else에서 start가 결정되고, 마지막 else에서 end가 결정
        {
            ni[0] = min(ni[0], ints[i][0]);
            ni[1] = max(ni[1], ints[i][1]);
        }
        //else 의 의미를 더 생각해보자면,
        //interval[i][0] <= new_interval[1] : new의 end가 가능한 범위
        //interval[i][1] >= new_interval[0] : interval 값이 new의 start를 넘어야 new의 범위 안에 들어온 것
    }
    
    res.push_back(ni); //정해진 start와 end 범위를 삽입
    res.insert(end(res), begin(ints) + i, end(ints)); //end 이후 남아 있는 interval 요소들을 삽입한다.
    return res; 
   
    }
};

Identifying the Problem

시작과 끝의 간격이 주어져 있는 2차원 배열의 겹치는 부분을 최소화하여 리턴한다.

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]

Explanation: [1,3] 과 [2,6] 겹치므로, [1,6]으로 합침

Input: intervals = [[1,4],[4,5]] Output: [[1,5]]

Explanation: [1,4] 과 [4,5] 4가 겹치므로 [1,5]로 합침

Organizing thoughts

1. intervals 배열 정렬된 상태가 아니기에, 시작점이 작은 순서대로 정렬한다.

2. 초기 interval 2쌍을 초기 시작과 끝 값으로 대입하고, 다음 interval과 비교를 시작한다.  
3. intervals만큼 반복문을 진행하며 시작점과 기준값의 종료점을 비교하고 정한다.  

3. 시작과 끝을 정하는 과정

  a) 끝이 탐색 값의 시작 값 보다 더 크거나 같은 경우
     범위가 겹치는 경우이므로 start는 최소값 end는 최댓값으로 설정하고

     정답에 추가한다.

     여기서 주의할 점은 연속해서 겹치는 경우

     정답을 추가해주는 것이 아니라, 바뀐 start와 end를 업데이트 해준다고 봐야 한다.

     따라서 이 때는 이전에 추가한 배열을 지워준다.


  b) 그 반대의 경우
  겹치지 않는 경우이므로, 탐색하는 interval을 그대로 추가한다.

4. 정해진 시작 값과 끝 값을 정답에 추가한다.

Sourcecode

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans; //정답 배열
        vector<int> merge; //처음 값과 끝 값을 저장할 배열
        sort(begin(intervals), end(intervals)); //첫 값 기준 오름차순 정렬
        
        ans.push_back(intervals[0]); //초기값 설정
        
        merge.push_back(intervals[0][0]); //초기 start
        merge.push_back(intervals[0][1]); //초기 end
         
       
        
        
        for(int k = 0 , int i=1; i<intervals.size();i++)
        {
            if(merge[1] >= intervals[i][0]) //겹친 경우
            {    
                ans.erase(ans.begin()+k); //기존 겹친 경우를 지워주고
                merge[1] = max(intervals[i][1],merge[1]);
                merge[0] = min(intervals[i][0],merge[0]);
            }   
            else //안 겹친 경우
            {
                merge[0] = intervals[i][0]; //그대로 진행
                merge[1] = intervals[i][1];
                k++; //ans의 index 증가
            }
                
                
            ans.push_back(merge);  //결정된 처음과 끝 추가
        }
        
        
        return ans;
    }
};

Identifying the Problem

최대 nums의 값만큼 다음 index로 넘어가 끝까지 도달하면 true 도달하지 못하면 false 를 리턴한다.

Ex : Input: nums = [2,3,1,1,4] Output: true

Explanation: nums[0]에서 1칸 or 2칸 점프가능하고, 2칸 점프했을 때, nums[2] 에서 1칸 점프, nums[3]에서 1칸 점프                      nums[4] 도달하므로 true

Input: nums = [3,2,1,0,4] Output: false

Explanation: nums[3] 에서 0이고 더 이상 진행이 불가능하다.

Organizing thoughts

size가 1일 때에는 무조건 true 가 되도록 하고, 그 이후를 어떻게 하면 좋을지 생각해보자

예시에서 보았듯 nums[i] 가 무슨 값인지에 따라, nums가 진행가능한 범위가 정해진다.

즉 진행가능한 범위에 nums의 마지막 index가 들어오면 true를 리턴하고, 불가능하면 false 리턴하면 된다.

Sourcecode

dp 를 사용해 직접 작성한 코드이다.

하지만 시간복잡도가 O(n²) 이므로 Time Limit Exceeded가 떴다.

class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        vector<int> dp(nums.size(),0);
        
        dp[0] = 1; //초기값 true
        
        for(int i=0; i<nums.size()-1 ; i++) //마지막 이전까지 진행
        {    
            if(dp[i] > 0) //index가 범위 안에 있다면
            {   
                for(int k=0; k<nums[i]; k++) //해당 index가 더 나아갈 수 있는 범위를
                    if(i+1+k < nums.size())  //size를 벗어나지 않는 선에서 추가한다.
                        dp[i+1+k] = 1;
            }
        
        }
            
        return dp[nums.size() - 1]; //마지막이 범위에 들어오는지 아닌지에 따라 true / false
    }
};

아래는 가장 간단하고 직관적인 코드이다.

출처 

bool canJump(vector<int>& nums) {
    int size=nums.size();
    int step=nums[0];
    //nums의 값만큼 앞으로 갈 수있게 step 설정
    
    for(int i=1;i<size;++i){ 
        step--; //다음 index로 넘어갈 때마다 step 감소
        if(step<0) //step 이 0보다 작아지면, 더 나아갈 수 없으므로 false
           return false;
           
        if(nums[i]>step) // nums[i] 값이 step보다 크다면 더 많이 나아갈 수 있으므로 step 교체
           step=nums[i];
    }
    
    return true; //defalut 값 true
}

Identifying the Problem

주어진 숫자 문자열 s에서 만들 수 있는 알파벳 조합의 개수를 구한다.

01은 1이 아니므로 알파벳 취급하지 않는다.

예를 들어

s = 11106 이라면

1/1/1/0/6 X

11/1/0/6 X

1/11/0/6 X

1/1/10/6 -> AAJF

1/1/1/06 X

11/10/6 -> KJF

1/11/06 X

이므로 정답은 2가 된다.

Organizing thoughts

생각해 볼 점은 문자를 1개 또는 2개 단위로 검사하고

1개 단위로 검사할 때는 문자가 0이면 안 된다.

2개 단위로 검사할 때는 두 문자가 10과 26 사이의 값이어야 한다.

그렇다면 s를 1과 2로 자연수 분할 한 모든 경우의 수대로 구하면 될 것 같다.

하지만, 1/1/1/0/6 이 안 되는 것을 이미 알고 있는 상황에서,

11/1/0/6 을 또 검사할 필요는 없는 것 같다.

이럴 때 생각나는 것이 DP이다.

1부터 11106까지 결과를 저장해야 하나? 이거는 아닌 듯하다.

s[0] ~ s[n-1] 까지 결과를 저장하는 것이 올바른 접근 방법인 것 같다.

1은 0이 아니니 1개가 만들어진다.

dp[0]은 1이 된다.

11은 1/ 에 '1'이 추가된 것 또는 null/ 에 '11'이 추가된 것이므로

1개 단위는 1이고 dp[0]과 같다.

2개 단위는 null/ 에 '11'이 추가된 것이므로

dp[1]은 dp[0] + dp[-1]개가 된다. (일단은 dp[-1] = 1이 있다고 치자)

111은 1/1 에 '1'이 추가된 것 또는 1/ 에 '11'이 추가된 것이므로

1개 단위는 1이고 dp[1]과 같다.

2개 단위는 '1' 에 '11'이 추가된 것이므로

dp[2]은 dp[1] + dp[0]개가 된다.

111은 1/1 에 '1'이 추가된 것 또는 1/ 에 '11'이 추가된 것이므로

1개 단위는 1이고 dp[1]과 같다.

2개 단위는 '1' 에 '11'이 추가된 것이므로

dp[2]은 dp[1] + dp[0]개가 된다. 

여기서 중요하다.

1110은 1/1/1 에 '0'이 추가된 것 또는 1/1 에 '10'이 추가된 것이므로

1개 단위는 '0'이 추가됐기에 불가능하고,

2개 단위는 '1/1' 에 '11'이 추가 된 것이므로

dp[3]은 dp[1] 개가 된다.

11106은 1/1/1/0 에 '6'이 추가된 것 또는 1/1/1 에 '06'이 추가된 것이므로

1개 단위는 이전과 같고, 2개 단위는 '1/1/1' 에 '06'이 추가된 것은 불가능하므로

dp[4]은 dp[3] 개가 된다. 

최종 dp는 [1,2,3,2,2] 이 된다.

그렇다면 초기값은 어떻게 설정할까?

아까 dp[-1] = 1이 있었다고 가정했다. 

하지만 index가 -1이 되는 것은 불가능하기 때문에

dp의 길이를 n+1로 선언하고, dp[n]에 1을 대입 후 위 방식을 거꾸로 진행하면 된다.

따라서 초기값은 dp[n] = 1만 설정하고,

dp[n-1] 을 탐색할 때에는 두 자리 단위 검사를 패스하게 조건을 맞추어준다.

Sourcecode

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n+1,0);
        //size+1로 dp를 선언하는 이유는 처음 1자리 수 검사를 할 때,
        //끝 자리가 0인지 아닌지에 따라 초기값이 바뀌기에
        //dp[n]을 1로 설정해 dp[n-1]에서 1을 끌고 가는지 아닌지 정한다.
        
        dp[n] = 1;
        
        for(int i = n-1; i>=0; i--)
        {
            if(s[i] != '0') //한 자리 단위 검사
                dp[i] += dp[i+1];
            if(i<n-1 && (s[i] == '1' || s[i] == '2' && s[i+1] <= '6'))
                dp[i] += dp[i+2]; //두 자리 단위 검사
            
        }
        return dp[0];
    }
};

Identifying the Problem

m x n인 행렬의 왼쪽 위에서 오른쪽 아래로 가는 최단 경로의 개수를 구한다.

Organizing thoughts

보자마자 고등학교 확통 경우의 수 문제임을 알고, 똑같은 풀이를 생각했다.

풀이법은 간단하다.

기준점의 행과 열로 가는 경우의 수는 모두 1이고

나머지 칸들은 칸 기준 왼쪽 칸으로 가는 경우의 수와 위 칸으로 가는 경우의 수의 합이다.

예를 들어 2 x 3 이라면,

이렇게 된다.

따라서

1. 2 x 3 행렬을 하나 만들고

2. 2 x 3 행렬을 모두 1로 초기화

3. dp[1][1] 부터 dp[n-1][n-1]까지 대각선(왼쪽 , 위) 합을 구한다.

4. dp[n-1][n-1] 을 리턴한다.

Sourcecode

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,1)); // m x n 인 2차원 벡터 행렬 선언
        
        for(int i = 1; i<m; i++)
            for(int k = 1; k<n; k++)
                    dp[i][k] = dp[i][k-1] + dp[i-1][k]; //대각합을 구하는 과정
        
        return dp[m-1][n-1];
    }
};

Identifying the Problem

문자열 s, t에서 t의 모든 문자가 포함되는 s의 부분 문자열들 중 최소 길이를 가지는 연속 부분 문자열을 구한다.

만약 정답이 없다면 빈 문자열 리턴한다.

Organizing thoughts

Sourcecode

이 코드는 내가 작성한 코드인데, O(n²)가 되어 매우 긴 경우 오류가 난다.

class Solution {
public:
    string minWindow(string s, string t) 
    {
        int t_lettermap[128] = {0};
        int w_lettermap[128] = {0};
        
        int s_len = s.length();
        int t_len = t.length();
        int left = 0;
        int right = 0;
        
        int min = s_len;
        string ans = "";
        
        if(s.compare(t) == 0) return s;
        else if(t_len > s_len) return "";
        else if(t_len == 1 && s_len == 1 && s[0] != t[0]) return "";
        
        for(int i =0; i<t_len; i++)
            t_lettermap[t[i]] +=1;
        
        while(left <= s_len - t_len)
        {
            w_lettermap[s[right]] += 1;
            
            if(left == 0 && right == s_len && !flag(w_lettermap, t_lettermap, t))
            { return "";}
            
            if(flag(w_lettermap, t_lettermap, t))
            {
                
                if(right - left + 1 <= min)
                {
                    min = right - left + 1;
                    ans = s.substr(left,right-left+1);
                }
                
                left++;
                right = left;
                memset(w_lettermap,0,sizeof(w_lettermap));
            }
            
            else right++;
          
            
            if(right == s_len)
            {
                left++;
                right = left;
                memset(w_lettermap,0,sizeof(w_lettermap));
            }
            
            
        }
    
        
        return ans;
    }
    bool flag(int* w_map, int* t_map, string t)
    {
        for(int i=0; i<t.length();i++)
        {
            if(w_map[t[i]] < t_map[t[i]])
            { return false;}
        }
        
        return true;
    }
};

가장 심플한 버전의 코드 (출처 : solution - v1s1on )

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> hist(128, 0);
        for (char c : t) hist[c]++;
        
        int remaining = t.length();
        int left = 0, right = 0, minStart = 0, minLen = numeric_limits<int>::max(); 
        									//int의 최대값
        while (right < s.length()){
            if (--hist[s[right++]] >= 0) remaining--;
            while (remaining == 0){
                if (right - left < minLen){
                    minLen = right - left;
                    minStart = left;
                }
                if (++hist[s[left++]] > 0) remaining++;
            }
        }
            
        return minLen < numeric_limits<int>::max() ? s.substr(minStart, minLen) : "";
    }
            

};

New things learned

하나의 반복이 끝났을 때, 초기화할 변수는 없는지 다시 한번 생각해보자

Identifying the Problem

주어진 문자열 s에서 최대 k번 문자열을 교체하여 가능한 가장 긴 중복 문자열의 길이를 리턴한다.

Input: s = "AABABBA", k = 1 Output: 4

Explanation: 4번째 A를 B로 1번 교체하므로 길이가 4인 BBBB 가장 긴 중복 수열을 만들었다.

Organizing thoughts

핵심 아이디어는 아래 유튜브를 참고했다.

Sourcecode

소스코드 출처

class Solution {
public:
    int characterReplacement(string s, int k) {
        
        int sl = s.length(); // 문자열의 길이
        
        vector<int>char_freq(26,0); //A~Z의 빈도를 저장할 LetterMap
        
        int result = INT_MIN; //결과 값
        
        //투 포인터
        int first = 0;
        int last =  0;
        
        // 저장한 빈도 중 가장 큰 빈도를 저장할 변수
        int max_freq = 0;
        
       // last 포인터가 끝까지 갈 때까지 반복
        while(last < sl)
        {
            char_freq[s[last]-'A']++; // 탐색 글자의 빈도 증가
            max_freq = max(max_freq,char_freq[s[last]-'A']); 
            //문자열 중 가장 큰 빈도를 가진 문자의 개수

            // window 크기 - max_freq 가 k 보다 작으면 window의 크기를 넓히면 되지만
            // k보다 클 경우 window의 크기를 줄여야한다.
            if((last-first+1 - max_freq)> k)
            {
                char_freq[s[first]-'A']--; //windown를 오른쪽으로 옮기면서                 
                first++;	//왼쪽 빈도 줄이기
            }

            result = max(result,last-first+1); //window길이와 이전 max의 값을 비교
            last++; //window 크기 증가
        }
        
        return result;
    }
};

New things learned

Identifying the Problem

주어진 2차원 문자열 board에서 각 요소를 가로 또는 세로로 이어 주어진 word를 만들 수 있는지 판단한다.

EX ) Input: word = "ABCCED" → Output: true

Organizing thoughts

아래 유튜브 영상의 해설을 참고하여 작성하였다.

핵심 아이디어는 우선깊이탐색 (DFS) 를 사용해 탐색한 부분은 흔적을 남기고,

재귀로 반복하며, 다음 글자와 일치하는 경우 count를 증가하며 탐색했다.

Sourcecode

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) 
    {
        for(int i=0; i<board.size(); i++) //board 전체를 탐색
        {
            for(int k=0; k<board[i].size(); k++)
            {
                if(board[i][k] == word.at(0) && dfs(board,i,k,0,word)) 
                    return true; //첫 글자와 board 탐색 값이 같고, 
                    			 //dfs결과 값이 true인 경우 true 리턴
            }
        }
        return false; //default 값 false
    }

public: //글자가 같은 경우 흔적을
    bool dfs(vector<vector<char>>& board, int i, int k, int count, string word)
    {
        if(count == word.size()) //탐색한 글자의 수가 word와 일치하면 true 리턴
            return true;
        
        if(i<0 || i>= board.size() || k<0 || k>=board[i].size() || board[i][k] != word.at(count))
            return false; //탐색하는 요소의 범위가 board의 범위를 벗어나거나
            			  //탐색하는 요소의 값과 글자가 다른 경우 false를 리턴한다.
        				  //이미 지나갔던 부분은 ' '로 흔적을 남겼기에 글자가 다른 경우에 포함한다.
        
        char temp = board[i][k]; //현재 탐색하는 값을 temp에 저장하고
        board[i][k] = ' '; //탐색했던 흔적을 남긴다.
        
        bool found = 
            dfs(board, i+1, k, count+1, word) || 
            dfs(board, i-1, k, count+1, word) ||
            dfs(board, i, k+1, count+1, word) ||
            dfs(board, i, k-1, count+1, word);
            //상하좌우로 재귀로 탐색한다.
        
        board[i][k] = temp; //지웠던 탐색값을 원래대로 되돌린다.
        
        return found;
    }
    
};

New things learned

• 우선 깊이 탐색 (DFS

Identifying the Problem

주어진 두 문자열이 anagram인지 확인

anagram이란, 하나의 단어의 구성 문자들로 만들어진 새로운 단어를 말한다.

Organizing thoughts

1. s와 t를 오름차순 정렬하고, 두문자가 같은지 파악하는 방법

2. lettermap을 사용해 알파벳의 개수가 같은지 파악하는 방법

2번이 더 간단해서 2번으로 풀었다.

Sourcecode

bool isAnagram(char * s, char * t)
{
    int letterMap_s[128] = {0}; //s와 t의 lettermap
    int letterMap_t[128] = {0};
    
    int len_s = strlen(s); // s와 t 길이 파악
    int len_t = strlen(t);
    
    if(len_s != len_t) return false; //두 단어의 길이가 다르면 false
    
    for(int i =0; i<len_s; i++) //lettermap에 각 문자들의 개수 파악
    {
        letterMap_s[s[i]] +=1;
        letterMap_t[t[i]] +=1;
    }
    
    for(int i=0; i<128; i++)
    {
        if(letterMap_s[i] != letterMap_t[i]) return false;
        //문자의 개수가 다른 경우 false
    }
    
    
    
    return true; //defalut 값 true
}

Identifying the Problem

주어진 문자열 s에서 중복되는 문자가 없는 Substring의 길이를 구한다.

Sourcecode

int lengthOfLongestSubstring(char * s)
{
    int letterMap[128] = {0};
    int max = 0;
    char* start = s;
    char* end = s;
    
    while(*end)
    {
        if(letterMap[*end] != 0) //탐색 값이 중복일 때
        {
            max = (end-start) > max ? (end - start) : max;
            // 중복을 찾은 지점과 처음 지점의 차이 = Substring 길이
            // Substring가 max보다 크면 max에 단어길이 저장
            while(*start != *end)
            {
                letterMap[*start] = 0; //Substring에 있던 글자들 0으로 초기화
                start++; //Substring 의 탐색지점 이동 ex(abc 였으면 a->b->c)
            }
            
            start++; //시작점을 중복이었던 부분으로 이동
            
        }
        
        else //탐색 값이 중복 아닐 때
        {
            letterMap[*end] = 1; //해당 문자가 있었다고 표시
        }
        
        end++; //탐색 값 다음 위치로
    }
    return (end-start) > max ? (end - start) : max;
    // 중복이었던 경우가 아예 없었더라면, end-start가 max값이 됨
}

New things learned

• 포인터의 위치차로 단어의 길이를 구하는 방법이 신박했다.
• 시간복잡도를 줄이는 방법 중 하나는 사용하는 메모리를 늘리는 것이다.
• O(n₃)인 풀이에서 중복인 부분을 판단하는데 반복문을 사용하는데,
  이 풀이에서 letterMap을 사용해 중복이었는지 아닌지 판단했다.

Identifying the Problem

주어진 matrix를 90도 회전한다.

단, 새로운 matrix를 생성하면 안 된다.

Organizing thoughts

어렷을 때 슬라이딩 퍼즐 가지고 논게 문제푸는 데 도움이 된 것 같다.

이런 경우

옆에 두칸을 [2,3]으로 따로 빼두고,
1을 3번자리로 옮기고,

4를 2번자리로 옮기고

7을 1번 자리로 옮기고

8을 4번 자리로 옮기고

...

6을 8번 자리로 옮긴다.

이후, 6번과 9번 자리에 2,3을 집어 넣는다.

이를 양파 까듯 n x n 테두리, (n-2) x (n-2) ... 1 x 1 까지 반복한다.

Sourcecode

void rotate(int** matrix, int matrixSize, int* matrixColSize)
{
    int n = matrixSize;
    int* store = malloc(sizeof(int) * (n-1)); //위 끝을 저장할 배열
    
    for(int i=0; i<(n+1)/2; i++)
    {
        for(int k = i+1; k<= n-i-1; k++)
            store[k-i-1] = matrix[i][k]; // 위 끝값 저장
        
       
        for(int k = 0 ; k< n-2*i; k++)
            matrix[i][n-1-k-i] = matrix[k+i][i]; // 위 끝을 왼 끝으로 채우기
        
       

        for(int k = 0 ; k< n-2*i; k++)
            matrix[k+i][i] = matrix[n-1-i][k+i]; //왼 끝을 아래 끝으로 채우기
        
     
        
        for(int k = 0 ; k< n-2*i; k++)
            matrix[n-1-i][k+i] = matrix[n-1-k-i][n-1-i]; //아래 끝을 우끝으로 채우기

        
        for(int k = 0 ; k< n-2*i -1; k++)   
            matrix[k+1+i][n-1-i] = store[k]; //우끝을 저장한 위 끝으로 채우기
        
        
    }
}

Mistake

• 진행 횟수와 좌표의 위치는 다르기에 자세히 생각하기
  n x n -> (n-2) x (n-2) 과정에서 시작 점의 좌표를 0,0 그대로 했음

해설 코드 출처

https://leetcode.com/problems/word-break/discuss/1399968/C-Implemented-in-C-with-dynamic-programming%EF%BB%BF

Identifying the Problem

주어진 s를 wordDict상의 단어들로 만들 수 있는지 판단해

가능하면 true , 불가능하다면 false를 return한다.

Organizing thoughts

MAIN IDEA s의 길이가 n일 때

0, 0~1, 0~2,,, 0~n-1 ,0~n 를 worddict으로 만들 수 있는지 판단한다.

예를 들어 s 가 leetcode 면,

l를 worddict으로 만들 수 있는지

le를 worddict으로 만들 수 있는지

lee를 worddict으로 만들 수 있는지

leet를 worddict으로 만들 수 있는지

leetc를 worddict으로 만들 수 있는지

leetco를 worddict으로 만들 수 있는지

leetcod를 worddict으로 만들 수 있는지

leetcode를 worddict으로 만들 수 있는지 검사한다.

그리고 leetcode는 leet를 이미 worddict으로 만들 수 있기 때문에, 

code만 worddict으로 만들 수 있는지 판단한다.

Sourcecode

/*본인이 작성한 코드가 아님*/

bool wordBreak(char* s, char** wordDict, int wordDictSize)
{
    if(wordDict == NULL || wordDictSize==0 || s== NULL) 
    worddict이나, s 중//하나라도 아무것도 없으면 false return
    {
        return false;
    }
    
    int len = strlen(s) + 1;
    
    bool *hit = calloc(len, sizeof(bool)); //dp 생성
    
    hit[0] = true; //아무것도 없는거는 dict없어도 만들 수 있으니 true
    			   //초기값 설정 
                   
    for (int i = 0; i < len; i++) { //s 전체 길이만큼 탐색
        for (int j = 0; j < wordDictSize; j++) { //worddict 검사
            if(hit[i]) { //처음은 초기값 true이므로 검사
                
                int wordLen = strlen(wordDict[j]);

                char str[wordLen+1];
                strncpy(str, s+i, wordLen);
                str[wordLen]='\0';
                
                if(strcmp(str, wordDict[j]) == 0) {
                    hit[i+wordLen] = true; 
                    //worddict이 들어가니 탐색index + 단어 길이 dp[index]는 true
                }
            }
        }
    }
    return hit[len-1]; //s의 dp결과를 return
}

Mistake

뭔가 계속 이어져 가는데, 그 이어짐을 어떻게 이을지 답답했다.

나중에서야 dp로 풀면 간단했음을 알았다..