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

문자열 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

주어진 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

amount를 지불하는 최소한의 coin 개수를 구한다.

단 coins로 amount를 만들지 못할 경우 -1을 리턴한다.

Organizing thoughts

coins = [1,2,5] amount = 11인 경우

5개를 최대한 (2개)내고 , 나머지를 1로 (1개) 내는 방법이 있다.

11/5 + 1/2 + 1/1 = 3

하지만 coins = [2,3,6,7] amount = 12 인 경우

12/7 + 5/6 + 5/3 + 2/2 = 3개이지만,

6+6 = 12 으로 생각하면, 2개로 더 적은 coin이 사용된다.

따라서, amount에서 coin별로 값을 뱃을 때, 그 값이 필요한 동전의 개수를 파악하며 

조심스럽게 접근해야 한다.

즉 1 부터 amount까지의 개별로 필요한 coin의 수를 파악해야 한다.

11에서 5를 뺀 값 6을 최소한의 코인으로 얼마나 만들 수 있는지

6에서 5를 뺀 값 1을 최소한의 코인으로 얼마나 만들 수 있는지

그리고, 여기서 DP의 패턴을 발견 할 수 있다.

Sourcecode 

int cmp(const void *p1, const void *p2)
{
    return *(int *)p1 - *(int *)p2;
}

int find_min(int a , int b);

int coinChange(int* coins, int coinsSize, int amount)
{
  
	qsort(coins, coinsSize, sizeof(int), cmp); //coin 오름차순 정렬
    //coinSize인 이유 : coinsSize/sizeof(int)는 coinsSize가 배열인 경우 배열의 길이를 구하는 용도
    
    int* count = malloc(sizeof(int)  * (amount+1)); //0~amount까지의 count가 들어갈 배열
    
    int flag = 0; //주어진 코인으로 해당 수를 만들 수 있는지 판단하는 flag
    int min; 
    //12에서 7을 뺀 경우보다 6을 뺀 경우의 수가 더 적은 코인을 가져오기에
    //각 경우를 비교하기위해 min을 사용
    
    if(amount == 0) return 0; //아무것도 없는 경우 0리턴
    
    count[0] = 0; //초기 설정 0은 어차피 0개고
    count[1] = coins[0] == 1 ? 1 : -1; //1은 1이 있으면 1 없으면 -1로 유추 가능

    
    for(int i = 2; i<= amount; i++)
    {    for(int k = coinsSize-1; k>=0; k--) //큰 코인부터 줄여나감
        {
            int t = i - coins[k];
            
            if(t >= 0 && count[t] != -1 )
            {
                if(flag == 0) min = count[t]; 
                //min의 최소는 맨 처음 코인으로 가능한 경우 수
                
                min = find_min(min,count[t]);
                count[i] = min + 1; //최소한의 코인 개수 + coin[k] 이므로 + 1 
                flag = 1; //주어진 코인으로 i를 제작할 수 있으니 flag 세움
            }
            else if (flag == 0) // flag
               count[i] = -1;
            
       
        }
        
        flag = 0; //flag 0으로 되돌려줌
       
     }
    
    return count[amount]; //마지막 count를 구한다.
}

int find_min(int a , int b) //min 함수
{
    if(a<b) return a;
    else return b;
}

Identifying the Problem

최빈값을 찾아라

단 최빈값은 배열 길이 절반 이상 있다.

Input: nums = [3,2,3] Output: 3

Input: nums = [2,2,1,1,1,2,2] Output: 2

Organizing thoughts

바로 떠오르는 알고리즘이 있긴 한데, O(n²)로 상당히 복잡하고 뻔함
그래서 발견한 게 Boyer-Moore 알고리즘임

그림만 봐도 직관적으로 이해가 된다.

main idea : count 가 가장 높았을 때, major의 값이 return 된다.

1. 1부터 마지막만큼 반복하면서

2. major와 nums [i]가 같다면
    2-1 count를 증가 

3. 다르다면
    3-1 count--;

4. count 가 0이 되는 순간 major =  nums[i]
5. major값을 return

Sourcecode

int majorityElement(int* nums, int numsSize)
{
    int major = nums[0];
    int count = 1;
    
    for(int i=1; i<numsSize; i++) //1
    {
        if(major == nums[i]) //2
            count++;
        else                //3
            count--;
        
        if(count == 0)  //4
        {
            major = nums[i];
            count++;
            
        }   
    }
    
    return major; //5
}

New things learned

• Boyer-Moore 알고리즘

Identifying the Problem

주어진 정수에 해당하는 엑셀 상의 열의 위치를 문자로 리턴한다.

Constraints:

• 1 <= columnNumber <= 2^31 - 1

1 -> A
2 -> B
3 -> C ...
26 -> Z
27 -> AA
28 -> AB...

Organizing thoughts

아이디어는 간단하다.

10진수를 알파벳으로 표현하는 26진수 숫자로 바꾸면 된다.

진수를 변환하는 과정은 지난 문제에서 풀었기에 따로 기술하진 않겠다.

다만 가장 낮은 자릿수부터 누적시키기 때문에, 끝까지 누적시키고 나서 

배열을 뒤집어야 한다.

Sourcecode

char * convertToTitle(int columnNumber){

    

    char* answer = malloc(sizeof(char) * 8); //2^31 - 1 일 때 문자의 길이는 8이다.
    strcpy(answer,"");
    int x;
    char tmp;
    
    while(columnNumber != 0) //진수 변환 과정
    {

        x=columnNumber%26;
        
        if(x==0) x=26;

        tmp = x+'A'-1;
        
        strcat(answer,&tmp);

        if(columnNumber%26==0) columnNumber--;
 
        columnNumber/=26;

    }

    int len = strlen(answer);

    for(int i=0;i<len/2;i++) //뒤집는 과정

    {   

        tmp = answer[i];
        answer[i] = answer[len-1-i]; 
        answer[len-1-i] = tmp;     

    }
    
    return answer;
}

Mistake   

  if(columnNumber%26==0) columnNumber-- 이 부분에서 왜 1을 감소시키는 걸까?

한 예를 들어보자 702는 'ZZ' 이다 

x = 702%26 = 0
x가 0이므로
tmp = z
answer에는 z가 누적
columnNumber/=26 이므로 나머지 27이 된다.
        
x = 27%26 = 1
tmp = z 다음 아스키코드
answer에는 다음 아스키코드가 누적된다.

이처럼 이전의 나머지가 0이었던 경우, 몫에 26이 한번 더 들어가게 되기 때문에 1을 빼줘야 한다.

Identifying the Problem

마지막에서 n번째위치한 node 제거

Organizing thoughts

1. 마지막 노드 index를 파악하고

2. index-n-1번 노드 (제거할 노드 이전 index) 와 index-n+1(제거할 노드 다음 index) 노드를 연결한다.

Mistake

• listnode = [1,2]  n = 1 일 때 [1,2] 가 나왔다.
  두번째 for 문의 탈출조건을 temp로 했는데, link->next = temp 를 하지못하고 탈출해버렸다.
  그래서 탈출조건을 temp 에서 k<=i로 바꾸었다.

• listnode = [1,2]  n = 2 일 때 에러가 나왔다.
  if(i-n-1 == k) 부분에서 -1 == k 가 되면서 link의 주소가 지정되지 않았다.
  그래서 전체길이와 n의 길이가 같을 때, 처음거만 패스한 주소를 리턴하게 했다.

Sourcecode

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    int i=0;
    struct ListNode* temp = head;
    struct ListNode* link;
    struct ListNode* ans = head;
    
    if(head->next == NULL) return NULL;
    
    for(i=0;head;i++)
    {
        head = head->next;
    }
    
    if(n==i) return ans->next;
    
       
    for(int k=0; k<=i ; k++)
    {
        if(i-n-1 == k)
            link = temp;
        if(i-n+1 == k)
            link->next = temp;
        if(k<i)
            temp = temp->next;
    }
    
    return ans;
    
}

Identifying the Problem

32bit 정수 x를 뒤집어 return한다. 정수 x가 32bit 을 초과할 경우 0을 return 한다.

Organizing thoughts

0. 음수일 경우 임시로 양수로 바꾸고, 마지막에 다시 음수로 바꿔준다.

1. 자리수 알아내기

1-1 <자리수 -1번 반복> x를 10으로 나눴는데 0이면 탈출, 아니라면 n++ (n초기값 1)

1-2 자리수만큼 ten 변수에 10을 곱해 자리수를 맞춰준다.

2. 일의 자리에서 백의 자리 쪽으로 자리수 추출

3. answer 에 num * ten 을 누적해서 더하고 ten을 10으로 나눔으로 자리수를 줄인다.

4. 만약 마지막 시도라면 answer에 x만 더한다.

5. 뒤집은 값이 범위를 초과 시, answer에 0을 대입한다.

6. answer 를 return 한다.

제약조건은 다음과 같다.

x 값 범위 [-2^31, 2^31 - 1]

Sourcecode

int reverse(long long int x){

    long long int ten =1; //자리수 맞추기용 
    long long int n = 0; //자리수
    long long int temp  = x; //자리수 구할 때 사용할 x값
    long long int num = 0; //추출된 숫자
    long long int answer = 0; // 정답
    long long int flag = 0; // 음수여부를 판단하는 flag

     


if(x<0)                  //0번
	flag =1; x= x*(-1);
    
while(1)                //1번
{
   	temp /= 10;
   	if(temp == 0) break;
   	else {ten*=10; n++;}
}
    
if(x>9) 
{
	for(int i=0; i<n; i++)
    {
    	num = x%10;   //2번
    	x = x/10;
     	answer += (num*ten); //3번
    	ten = ten/10; //자리수를 낮춘다. 
    
    	if(i==n-1) answer +=x; //4번
     
    }
    
    if(flag ==1) {answer = answer*(-1);}
}

else if (x<10) answer =x; //1의 자리는 따로 과정을 밟지 않도록 한다.

if(answer>2147483647||answer<-2147483646)  answer = 0; //5번
    return  answer;
}

Mistake

• 처음 x가 들어왔을 때 32bit 범위를 초과시 0을 return 하게 했는데, 뒤집은 결과 값도 32bit 범위를 초과하면 안 되었다.
• x 가 음수일 경우를 생각 못했다.

New things learned

• 일의 자리인 경우 바로 return을 해도 되지만, 음수인 일의 자리인 경우도 있어 마지막에 처리하였다.

Identifying the Problem

nums 정수 배열 안의 두 수의 합이 target과 같다면, 해당 두 수의 index를 정수 배열 형태로 리턴한다.예를 들어 nums = [2,7,11,15], target = 9 라면, 리턴 값은 [0,1]이 된다.

제약 조건은 다음과 같다.

• 2 <= 정수 배열 길이 <= 10^4
• -10^9 <= 배열 안의 요소 값 <= 10^9
• -10^9 <= target <= 10^9 

Organizing thoughts

제약조건은 int 범위를 만족하므로 따로 long int 를 사용하지 않았다.

0. 정답 배열을 선언하고, 동적할당을 한다.

1. 중첩 반복문을 사용해 0번 + 1번, 0번 + 2번 .... numsSize-2번 + numsSize-1번의 값을 구한다.

1-1 중첩 반복시 n번은 n+1번부터 비교한다.

2. target과 동일할 시 해당 index 둘을 정답 배열에 넣고, 반복을 중단한다. 

3. 결과를 return 한다.

Sourcecode

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    int * answer = malloc(sizeof(int)*8); //0번 
    *returnSize = 2;
    
    
    for(int i=0; i<numsSize - 1; i++) //1번 nums[numsSize]는 메모리 초과이므로 끝에서 두번째까지만
        for(int j=i+1; j<numsSize; j++)
            if(nums[i]+nums[j] ==target) //2번 
            {
            	*(answer) = i;
                *(answer+1) = j;
             	break;
            }
            
    return answer; //3번
}

Mistake

for(int j=i+1; j<numsSize; j++ ) 에서 j=i+1 부분을 j=0부터 시작해 중복해서 

nums[0] 과 nums[0] 을 더하는 실수를 했다.

New things learned

int 의 범위 : –2,147,483,648 ~ 2,147,483,647

동적할당 : int* nums = malloc(sizeof(int) * 길이) -> 이후 free(nums)

배열길이 구하기 : len = sizeof(arr) / sizeof(int)

컴공 1학년을 마치고 바로 군대에 들어온 터라 내가 컴공이 맞는지도 잘 모르겠다,, ㅎㅎ

최종 목적지는 "퀀트 & 데이터 사이언티스트" 이지만, 기초부터 탄탄히 하고싶어 

LEETCODE를 풀게 되었다. 

풀이 언어는 C로 풀다가 나중에 C++로 풀이하겠다.

(아직 C++을 배우는 중이라,,,ㅎㅎ) 

1일 2문제 풀도록 노력할거고, 훈련이나 풀근무 서는 날은 블로그에 글을 올리지 못할 것 같다 ㅠㅠ

그래도 미리 문제, test case 적어가서 최대한 고민해보는 시간을 가져보도록 하겠다.

글 양식은 

제목 : 문제번호, 문제이름

내용 : 문제 이해하기/ 풀기 전 생각 최대한 정리하기/ 소스코드/ 실수한 점/ 새로 배운 점

이런 식으로 작성할 것이고, 도저히 풀지 못하겠는 문제 같은 경우는

다른 사람의 소스코드를 분석하면서 배우도록 하겠다.

풀다보니 자료구조를 충분히 이해해야만 풀 수 있는 문제 유형이 많아

자료구조도 병행하면서 풀어나갈 예정이다. 

파이팅!