Identifying the Problem

트리를 반으로 나눴을 때 대칭이 되는지 판단해 true, false를 return 한다.

Organizing thoughts

1. 자녀 계층 왼쪽과 오른쪽으로 나눠 시작한다.

1-1 왼쪽은 중위 순회를 왼쪽 우선, 오른쪽은 오른쪽 우선으로 탐색한다.

2. 둘 중 하나 null 이면 flag = false

3. 탐색 중 둘 다 값이 다르면 flag = false  

Sourcecode

void answer(struct TreeNode *l,struct TreeNode *r,int *f);

bool isSymmetric(struct TreeNode* root){
    
    struct TreeNode *l,*r;
    
    l = root->left;
    r = root->right;
    
    int flag = 1;
    answer(l,r,&flag);
    
    return flag;
}


void answer(struct TreeNode *l,struct TreeNode *r,int *f)
{


    if(!l && r) *f = 0;
    if(l && !r) *f = 0;
    
    else if(l && r)
    {
      if(l->val != r->val) *f = 0;
      answer(l->left,r->right,f);
      answer(l->right,r->left,f);

    }

}

Mistake

• return 값을 true로 한 경우와 false로 한 경우 코드가 꼬여서 복잡해지거나 에러가 난다.
  바로 true false로 하는 게 아니라 false 인 경우에만 flag를 세우는 방식으로 하니 이해가 편했다. 

Identifying the Problem

주어진 두 개의 이진트리 p, q를 비교해 같은 지 다른 지 비교해

같으면 true, 다르면 false를 return 한다.

Organizing thoughts

크게 두 가지 방법이 있는데,

1. 94번 문제의 p q 각각 answer를 만들고, answer끼리 비교한다.

2. p, q 둘 다 중위순회하면서 서로 같은지 비교하고, 다를 경우 false 가 되게한다.

2번이 더 간단하기에 2번을 채택했다.

Sourcecode

bool checkTree(struct TreeNode* p, struct TreeNode* q);

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if (!p && !q) return true; // 둘다 null                 
    else if (!p || !q) return false; //둘 중 하나만 null (xor)
    return checkTree(p, q);
}

bool checkTree(struct TreeNode* p, struct TreeNode* q) 
{
    if (!p && !q) return true; // both are null
    else if (!p || !q) return false; // one is null
    
    if (p->val != q->val || !checkTree(p->left, q->left) || !checkTree(p->right, q->right)) 
    	return false;
    
    // 1조건은 단순히 두 값이 다를 때
    // 2,3조건은 이중부정을 이용해 !false true 니깐, false 를 리턴 
    
    return true;
}

Identifying the Problem

이진트리의 중위 순회 진행하라.

Organizing thoughts

이진트리도 처음보는데, 중위 순회 만들라뇨,,

조건도 복잡하고, 자녀 트리에서 부모 트리로 어떻게 올라갈지도 갈피가 안 잡혀서 

답 보고 익혔다.

아래 블로그에 이진트리 설명 잘 돼 있어 참고했다.

Sourcecode

void inorder(struct TreeNode* root,int* answer, int* Size);

int* inorderTraversal(struct TreeNode* root, int* returnSize){

    int* answer = malloc(sizeof(int) * 256);
    *returnSize = 0;
    inorder(root, answer, returnSize);
        
    return answer;
}

void inorder(struct TreeNode* root,int* answer, int* Size)
{
    if(root!=NULL) //왼쪽이나 오른쪽의 값이 없을 경우, 이전 recursion으로 되돌아간다.
    {
        inorder(root->left, answer, Size); //왼쪽만 주구 장창 파내려간다.
        answer[*Size] = root->val; //값을 집어넣기
        (*(Size))++;// == *Size = *Size + 1 실수하기 쉬우니깐 오른쪽걸로 하는게 좋을 듯 함
        inorder(root->right, answer,Size);
        
        
    }
    else return;
    
}

Mistake

• (*(Size))++ 에서  실수하기 쉬우니깐 *Size = *Size + 1로 하는 게 좋을 듯하다.

Identifying the Problem

주어진 x의 제곱근을 구한다.

단, 소수점 이후는 잘라 나타내고, pow 함수는 사용하면 안 된다.

Constraints:

• 0 <= x <= 2^31 - 1

Input: x = 8

Output: 2

Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Organizing thoughts

직관적인 아이디어로 반복문을 사용해 i² == x 거나 i² 이 x를 초과하는 순간을 잡아내면 끝이긴 한데,

 x가 2^31 - 1 인 경우 엄청난 반복을 해야 하고, i를 제곱하는 과정에서 int의 허용범위를 벗어나는 경우가 생겼다.

따라서 다른 조건이나 패턴을 찾아보았다.

x를 절반으로 나눈 값은 x의 제곱근이 될 수 없다. 

라는 패턴을 찾을 수 있었다.

따라서 중앙값 기준으로 양끝을 조이면 된다.

1. 양 끝 기준으로 중앙값 mid을 정하고

2. mid² == x 인 경우 mid 리턴

3. mid² > x 인 경우 끝을 mid - 1로 줄인다.

4. mid² < x 인 경우 처음을 mid +1로 늘린다.

단 mid² 와 x를 비교하는 것은 int 범위를 벗어나므로 mid 와 x/mid를 비교한다.  

Sourcecode

int mySqrt(int x)
{



	if(x<2) {return x;}

	int first=1;
    	int end=x;
    	int mid=0;

	while(first<=end) //처음과 끝을 조이는 방식이기에 first가 증가되고 end 가 감소하다보면 
    				  //언젠간 만난다.
	{
        mid=first+(end-first)/2;
        		
		if(mid==x/mid)
			return mid;
        		
		if(mid<x/mid)
	        first=mid+1; //제곱값이 x에 도달하도록 처음값을 증가시킨다.
        		
      	  	else
	        end=mid-1; Q: 왜 과감하게 mid - 1 을 하는가? 
                        	A: 어차피 mid 보다 큰 값은 제곱근이 안된다.
        	
  	}
    	
        return end;
    
    
}

Identifying the Problem

자기 자신을 제외한 나머지 모든 곱을 수열로 리턴한다.

Input: nums = [1,2,3,4]

Output: [24,12,8,6]

Organizing thoughts

직관적인 방법으로 풀면 O(n²)로 금방 푼다.

하지만 어떤 문제를 풀든 O(n²) 보다 더 효율적으로 풀 수 있는 방법이 있다고 생각한다.

자세히 생각해 본 결과, 268 Missing number 문제의 알고리즘에서 해답을 얻었다. 

0~n까지 주어진 배열에서 빠진 숫자를 찾는 문제였다.

간단히 설명을 하면 0~n까지 다 더한 값과 수열을 다 더한 값을 뺏을 때 값이 답이었다.

게다가 0~n까지 다 더하는 과정은 등차수열 공식을 사용해 굳이 0~n 반복문을 하지 않아도 됐다.

각설하고 268번 문제의 아이디어를 그대로 따오면

1. 반복문으로 처음에 수열의 모든 값을 곱한다.

2. 그 다음 반복문에 모든 값을 곱한 값을 탐색 중인 수로 나눈다.

3. 나눈 값으로 탐색 중인 수열을 채운다.

하지만 nums = [-1,1,0,-3,3] 같은 경우는 index = 2에서
곱한 모든 값 / 0 = ? 으로 0으로 나누는 경우가 발생한다.

더 생각해보자

<수열 내 0이 1개인 경우>

0인 부분은 0이 아닌 수의 모든 곱을 넣으면 된다. 

0이 아닌 부분은 0을 넣으면 된다.

<수열 내 0이 2개인 경우>

모든 값이 0이 된다.

Sourcecode

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int multi = 1;
    int count = 0; //0의 개수
    
    *returnSize = numsSize;
   
    for(int i=0;i<numsSize ; i++)
    {        
        if(nums[i] !=0)
            multi *= nums[i];
        else 
            count ++;
    }
    
    for(int i=0;i<numsSize; i++)
    {   
        if(nums[i] !=0 && count ==0) //0이 없는 경우
            nums[i] = multi / nums[i];
        else if(nums[i] ==0 && count == 1) //0이 1개이고 0인경우
            nums[i] = multi;
        
        
        else //0이 2개 이상인 경우혹은 1개인데 0이 아닌 경우
            nums[i] = 0;
        

     }
    
    return nums;  
}

Mistake

신나게 다 짜 놓고 이 부분을 고려를 안 했다.

Identifying the Problem

happy number 인지 아닌지 판단해 true 혹은 false 값을 리턴한다.

happy number 란 각 자리수 별 제곱해 합하는 과정을 반복하다 보면 1이 되는 값이다.

Organizing thoughts

생각난 방법은 크게 3가지가 있다.

첫째 만들어진 모든 수를 배열에 저장하고,

       현재 값이 저장된 배열안에 있는지 판단한다. (중복이면 무한루프가 돌고 있다는 뜻)

둘째  만들어진 모든 수를 배열에 저장하고,

        배열을 탐색하는 index의 증가 값을 다르게 해 무한 루프인지 판단하는 방법

셋째 모든 값이 37이라는 특정한 값에서 무한루프가 도는 경우가 있는데

       37 loop에 빠지면 false 1이 만들어지면 true 를 리턴한다.

생각해본 결과 코드가 가장 간결하고, 복잡하지 않은 세번째 방법이 가장 좋아보였다.

1. n이 37이 아니면 루프를 돌게한다.

2. 각 자리별 제곱합을 구한다.

3. n에 제곱합을 대입한다.

4. n이 1이면 true 를 리턴 아니면 계속 루프를 돌게한다.

5. 큰 루프를 빠져나왔다는 뜻은 37이 됐다는 뜻이니 false를 return 한다.

Sourcecode

#include<cmath>

class Solution {
public:
    bool isHappy(int n) 
    {
        int sum = 0;
    
        
        while(n!=37)
        {
            while(n != 0)
            {
                sum += pow(n%10,2);
                n /= 10;
                
                
            }
            
            n = sum;
            if(n==1) return true;
            sum = 0;
        }
        return false;
    }
};

Mistake

새로운 n 마다 sum을 초기화 해줘야하는데 안해서 무한루프가 돎

New things learned

• 코드 관련한 건 아니지만, happy number 가 만들어지는 과정이 신기했다.
  아무리 큰 수더라도 happy number를 만들다 보면 작은 수로 수렴이 되는 것을 확인 할 수 이었다.
  이 작은 수안에서 계속 순환이 이뤄지는 것 같은데 특이점은 37 loop로 가기전에  전조증상으로 4가 나왔다.
  
  
• happy number 인지 판단하는 것과 자리수를 추출하는 과정 때문에 O(n²)가 되는 것은 어쩔 수 없는건가
  pow 함수를 썼으니 O(n³) 인건가?

Identifying the Problem

0부터 n까지 2진수로 바꾼 결과 1이 각각 1이 몇 개 있는지 배열로 리턴한다.

Organizing thoughts

뭐 어떻게 풀지 감이 안잡혀서 엑셀에 써놓고 보니깐 규칙이 보였다.

4 ~ 5은 2칸 앞의 값과 같고,

6 ~ 7은 2칸 앞의 값에 +1 한 값과 같다.

8 ~ 11은 4칸 앞의 값과 같고,

12 ~ 15은 4칸 앞의 값에 +1 한 값과 같다.

그러면 

16 ~ 16+8-1 은 8칸 앞의 값과 같고,

16+8 ~ 16+8+8-1 은 앞의 값에 +1 한 값과 같다.

슬슬 규칙이 보인다.

1. 4 이후부터

2. 해당 값이 간격 칸 앞과 같다가

3. 간격 칸만큼 반복이 진행된 후

4. 해당 값이 간격 칸 앞에 1을 더한 값과 같아진다.

5. 이후 간격 칸수는 2배씩 증가한다.

Sourcecode

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

/*


*/

int* countBits(int n, int* returnSize)
{

    int* ans = malloc(sizeof(int) * (n+1)); //정답 배열
    *returnSize = n+1;
    int two = 2; //간격 칸
    int two_count = 0; //처음 간격 칸
    int next_count = 0; // 이후 간격 칸
    
    for(int i=0;i<=n;i++)
    {
        if(i == 0) ans[i] = 0; //1. (0,1,2,3 은 pass)
        else if(i == 1) ans[i] = 1;
        else if(i == 2) ans[i] = 1;
        else if(i == 3) ans[i] = 2;
        
        else //4이상의 경우
        {
            if(two != two_count) 
            {   two_count++;
                ans[i] = ans[i-two]; //2
            }
            
            else  //3
            {
                ans[i] = ans[i-two] + 1; //4
                next_count++;
            }
            
            if(next_count == two) {two*=2; two_count=0; next_count=0; } //5
            
        }
        
    }
     
    return ans;
}

Mistake

0부터 n까지 해야하는걸 반복문에 습관적으로 0 <n으로 적었다.

New things learned

엑셀 나이스

Identifying the Problem

nums1과 nums2를 연결하고 오름차순 정렬한다.

Organizing thoughts

내 생각은 둘이 붙이고, bubble sort 하려 했는데

시간 복잡도 O(n+m) 인 방법도 있어서 다시 알아보았다.

Sourcecode (me)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int temp;
    
    
    for(int i=0;i<n;i++)
       *(nums1+m+i) = *(nums2+i);
    
    for(int i=0;i<nums1Size-1;i++)
    {
       for(int k=0;k<nums1Size-1-i;k++ )
           if(*(nums1+k) > *(nums1+k+1))
           { 
             temp = *(nums1+k);
             *(nums1+k) = *(nums1+k+1);
             *(nums1+k+1) = temp;

           }
     
    }
}

Sourcecode (other)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i=m-1, k=m+n-1, j=n-1; //i는 nums1의 마지막, j는 nums2의 마지막, k는 합배열의 마지막
    
    for (; k>=0 && i>=0 && j>=0;k--) //i,j,k가 모두 양수일 때만 반복, 
    								  
    {
        if (nums1[i] > nums2[j]) //nums1의 끝이 nums2 끝 보다 크면
        {
            nums1[k] = nums1[i]; //합배열의 끝을 nums1로 대입
            i--; //nums1 끝 index 앞쪽으로 (끝으로 보냈으니깐 볼일이 없지)
        }
        else //nums1의 끝이 nums2 끝 보다 같거나 작으면
        {
            nums1[k] = nums2[j]; //합배열의 끝을 nums1로 대입
            j--; 위와 마찬가지
        }
    }
    			// j가 먼저 음수가 돼 버리는 경우는 상관없지만,
    if (k >= 0) // nums1 [2,5,6] nums2 [1,2,3] 인 경우는 [2,2,2,3,5,6] 인 상태로 끝난다.
                // k가 0보다 크다는 말은 nums2가 정리가 안되었다는 말과 같다. 
    {
        for(;j>=0 && k>=0;j--,k--) //따라서 남은 k만큼 j를 정리해준다.
            nums1[k] = nums2[j];
    }
}

New things learned

하나의 배열안에 여러 가지 파라미터를 만들면 

시간 복잡도를 확연하게 줄일 수 있다는 사실을 알지만, 

내가 직접 생각하는 것은 쉽지 않은 것 같다.

Identifying the Problem

오름차순으로 주어진 linked list에서 중복되는 값을 제거한다.

Constraints:

• 노드 개수 [0, 300].
• -100 <= Node.val <= 100

Ex ) Input: head = [1,1,2,3,3]
     Output: [1,2,3]

Organizing thoughts

간단하다.

다음 값이 이전 값보다 높은 경우에만 이전 노드를 다음 노드와 연결 시키면 된다.

Sourcecode

struct ListNode* deleteDuplicates(struct ListNode* head){
    int num = -100;
    
struct ListNode answer;
    answer.next = NULL;
struct ListNode * ans = &answer;    
    
    
    
    while(head!=NULL)
    {
            
     if(head->val > num)
     {
     	num = head->val;
         
      	ans->next = head;
     	ans = ans->next;     
     }
            
     if(head->next == NULL&& head->val ==num) ans->next =NULL;
        
        
	head = head->next;
    }

    
    
    return answer.next;
}

Identifying the Problem

주어진 수열에서 가장 큰 부분 곱을 리턴한다.

Organizing thoughts

O(n²) 인 알고리즘으로 금방 푸는 문제지만, 다른 방법으로 어떻게 풀 지 

생각해봤는데 도저히 모르겠어서 정답을 참고했다.

코드는 의외로 간단하다.

수열이 다 양수면 상관이 없지만, 음수가 나오거나 0이 나오는 순간 굉장히 복잡해진다.

이런 것을 막기 위해 max 값과 min 값을 나눠서 구하는데

max 값은 왜 구하는지 직관적으로 이해가 가지만,

min 값은 왜 구하는지 도저히 이해가 안가서 Excel 로 수를 적어가니 알게 되었다.

최소값에 음수를 곱하는 순간 그 값이 최대값이 되기 때문이다.

최대값에만 메달려 있다보니, 이 생각을 미쳐 못한 것 같다.

따라서 최대값과 최소값은 탐색하는 1) 현재값 2) 가장 큰 곱과 현재값의 곱 3) 가장 작은 곱과 현재값의 곱 중에서 

선별된다.

Sourcecode

int max(int a,int b);
int min(int a,int b);


int maxProduct(int* nums, int numsSize)
{
    int max_val = nums[0];
    int min_val = nums[0];
    int ans = nums[0];
    int x,y;
        
    for(int i=1;i<numsSize;i++)
    {
        x = max(max(nums[i], max_val * nums[i]), min_val * nums[i]);  
       
        y = min(min(nums[i], max_val * nums[i]), min_val * nums[i]); 

        max_val = x;
        min_val = y;
        
        ans = max(max_val, ans); 
        
        
    }
    
    return ans;
}

int max(int a,int b)
{
    if(a>b) return a;
    else return b;
    
}
int min(int a,int b)
{
    if(a<b) return a;
    else return b;
    
}

Mistake

• max 값을 구하고 그 값을 min을 구하는 과정에 바로 넣어서 값이 이상하게 나오는 경우가 있었다. 
  코드의 흐름, 순서를 파악하는 것을 잊지말자.

New things learned

수열관련한 문제를 풀 때, 최소 최대를 이용하는 경우가 많은 것 같다.

심층적으로 생각해보자.

지난번 풀이에서 시간복잡도가 O(n₂)가 되어서 찝찝했는데,
다시 풀어보도록 하자.

Identifying the Problem

주어진 nums 배열에서 가장 큰 부분합을 찾아 return 한다.

Organizing thoughts

간단한 아이디어만 소개하면

0. 초기 max 값을 nums[0] 으로 초기화하고, 누적합은 0으로 초기화한다.,

1. 배열을 탐색하며 누적 합을 구하다

2. 누적합이 0이 되면 0으로 초기화 한다.

3. 만약 누적합이 max 값보다 크면 max에 누적값을 대입한다.

4. max 값을 리턴한다. 

Sourcecode

int maxSubArray(int* nums, int numsSize){

    int cur_sum = 0;
    int max = nums[0];
        
    for(int i = 0 ; i<numsSize; i++)
    {
        if(cur_sum < 0) cur_sum = 0;
        
        cur_sum += nums[i];
        
        if(cur_sum > max) max = cur_sum;  
    } 
    
    return max;
}

Mistake

누적합의 초기값과 max값의 초기값을 헷갈렸다.

핑계를 대자면 오늘 근무가 너무 힘들었다. 

Identifying the Problem

주어진 수열에서 없는 숫자를 파악한다.

ex [3,0,1] 이면 2가 없으니 2를 리턴한다.

Organizing thoughts

즉 배열의 수가 3칸이면 0,1,2,3 중 하나는 빠져있다는 거다.

그러면 전체가 다 있다는 가정하에

0부터 n까지 다 더한 합에서 수열의 합을 빼주면 어떤 수가 없는지 파악 할 수 있다. 

Sourcecode

int missingNumber(int* nums, int numsSize){

    int sum =0;
    
    for(int i=0;i<numsSize;i++)
    {
        sum += nums[i];
    }
    
    return (numsSize)*(numsSize+1)/2 - sum;
}

Identifying the Problem

계단을 한번에 1칸 혹은 2칸 오를 수 있을 때,

계단을 n 만큼 오를 수 있는 가능한 경우의 수를 구한다.

Organizing thoughts

가장 먼저 조합으로 풀릴 수 있을 거라 생각했고,

그렇게 해서 풀었지만, 가능한 펙토리얼의 한계가 있었고,

그걸 해결하려 식을 최대한 간소화 하는 작업도 했지만 double이 나타나는 값의 한계가 있었다.

따라서 정답을 참고해본 결과 경우의 수는 피보나치 수열을 따랐다.

Sourcecode

1. 펙토리얼의 규칙성을 찾아서 작성한 코드이다.

간단히 설명하면

n!/(x!y!) 이라고 했을 때 이 값을 sum에 누적 시킨다.

n은 매 차수마다 1씩 줄어들고,

x는 1을 n개 만큼 더한 변수이고, x의 초기값은 n과 같고 2씩 줄어든다.

y는 2의 개수이고, 초기 0부터 시작해 1씩 증가한다.

이 과정을 x가 0보다 작아질 때 까지 하면 된다.

int climbStairs(int n)
{
  /*int y = n;
  int z = 0;
  int sum = 0;
  
  int big;
  int small;
    
  if(n == 1) return 1;
    
  while(y>-1)
  {
      big = y; small = z;
      if(z>y){big = z; small = y;}
      
      sum +=multi(n,big,small);
      
      n = n - 1;
      y = y - 2;
      z = z + 1;
      
  }
  
      return sum;
}


int multi(int u,int b,int s)
{
  double ans = 1;
  
  while(u>b)
  {
   ans = ans*u/s;
   
   u--;
   s--;
  }

  return ans;
}

2. 피보나치 수열을 n까지 구한 값이다.

피보나치 수열을 간단히 설명하면

A[1] = 1

A[2] = 1 일 때,

n>2 이면 A[n] = A[n-2] + A[n-1] 을 만족하는 수열이다.

1. n<4 인경우는 n과 a[n] 값이 같아 그대로 리턴하고

2. 나머지는 피보나치 수열의 성질을 따라 작성한다.

int climbStairs(int n)
{

  int sum = 0;
    
   if(n<4) return n; //1
   int a = 1;
   int b = 2;
   int i = 3;
    
   while(i<=n) //2
   {
    sum = a+b;
    a = b;
    b = sum;

    i++;
   }



    return sum;
}

Mistake

언젠가는 100! 구하는 코드도 짜보자. 분하다.

New things learned

단순하게도 생각해보자.

Identifying the Problem

두 이진수 문자열을 더해 이진수 문자열을 return 한다.

Organizing thoughts

1. 일단 a 가 긴지, b가 긴지 몰라서 a를 긴 문자열로 정했다.

2. 자리수가 증가할 수 있으므로 a의 길이 + null 문자열 + 1 만큼 동적할당하였다.

3. a와 b의 상태를 파악하고 둘 더한 값을 stack 에 채워 넣는다.

3-1 stack은 채워지는 값을 뜻 하고, flag는 넘기는 수를 뜻 한다. 

a b 합이 1인 경우 flag을 올려 더 큰 자리수에 1을 넘겨 준다.

4. 이거를 표로 정리하면 다음과 같다.

5. sum 이 2이면 flag를 세우고, stack에 0을 채운다.

   sum 이 3이면 flag를 세우고, stack에 1을 채운다.

   0과 1 인경우는 stack에 0또는 1을 채운다.

6. sum는 매 시도마다 초기화 한다. 

7. 만들어진 stack을 뒤집는다. (이유는 가장 작은 자리수가 가장 큰 자리수가 되었기 때문이다)

Sourcecode

#include <string.h>
#include <stdlib.h>

char * addBinary(char * a, char * b){
    int a_l = strlen(a);
    int b_l = strlen(b);
    char * c;
    int flag = 0;
    int sum = 0;
    
    
    if(b_l>a_l) //1
    { 
        c = a;
        a = b;
        b = c;
        
        a_l = strlen(a);
        b_l = strlen(b);
        
    }
    
    char* stack = malloc(sizeof(char) * a_l + 2) ; //2
    
    *stack = 0;
    
    
    
    for(int i=0; i<a_l; i++)
    {
     if(a[a_l-1- i] == '1') sum += 1; //3
     if (flag ==1) sum += 1;
        
     if(i<b_l)
        if(b[b_l-1- i]=='1') sum += 1; 
     

      if(sum == 0)                     //5
      {  strcat(stack,"0"); flag = 0;}
        
      else if(sum == 1)
      {  strcat(stack,"1"); flag = 0;}
         
      else if(sum == 2)
      {  strcat(stack,"0"); flag = 1;}
         
      else if(sum == 3 )
      {  strcat(stack,"1"); flag = 1;}
    
        sum = 0; //6
     }
    
     if(flag == 1) 
         strcat(stack,"1");

    int len = strlen(stack) - 1;
          
    

   char tmp;
    
   for(int i=0;i<=len/2;i++)
   {
      tmp = *(stack+len-i);
      *(stack+len-i) = *(stack+i);
      *(stack+i) = tmp;
    
   }
 

   return stack;

}

Identifying the Problem

주어진 수열을 10진수라고 생각하고 +1한 값을 수열로 리턴한다.

Ex) [9,9] -> [1,0,0]

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

Organizing thoughts

1. 수열의 끝 부분을 +1 한다.

1-1 그대로 끝나거나

1-2 Ex) 처럼 자리수가 바뀌는 경우가 있다.

자리 수가 바뀐다 = 앞 자리가 9이다. 이므로

2. 앞자리가 9가 아니라면 더한 값을 리턴한다.

3. 앞자리가 9인 경우가 본게임이다.

999 같은 경우를 생각해보면

9 9 10 이 되고 

9 10 0 이 되고

10 0 0 이 되고

결국 1 0 0 0 이 된다.

이 과정에서 유추할 수 있는 것은

값이 10으로 바뀌면 0으로 초기화하고 이전 순서의 값을 +1 시킨다는 것이다.

그렇다면 첫 자리가 10이되면, 자리 수가 바뀌어야 되는데, 수열의 size는 int * 3 만큼 할당 되어있는 상태이다.

digitsize만큼 할당되어 있는 수열을 다시 동적할당 해야하는 건가?
 

라고 생각해 remalloc 하는 방법을 찾아서 고군분투했지만 더 좋은 방법이 떠올랐다.

4. 처음부터 degitSize + 1 만큼 동적할당을 한 정답 수열을 만들어 놓는 것이다.

4-1 다만 degitSize번 부분은 NULL로 두었다가 자리수가 바뀌면 이 부분을 0으로 채우면 된다.

Sourcecode

int* plusOne(int* digits, int digitsSize, int* returnSize){
 
    int n = digitsSize -1;
    int i=0;

    int* ret = (int*)malloc(sizeof(int)*(digitsSize+1));
    
    
    *returnSize = digitsSize;
    
    
    (*(digits+n))++;
    
    
    
    while(i<digitsSize)
    {
     *(ret+i) = *(digits+i);
     i++;
    }
   *(ret+i) = NULL; //4-1
    
    
    
    if(*(ret+n) == 10) //+1 을 한 결과 10이 된 경우
    {
        
        for(int i=n;i>0;i--)
        {
         if(*(ret+i) == 10)
         {
          *(ret+i) = 0; //0으로 초기화하고
          (*(ret+i-1))++; //이전 값을 +1 해준다

         }
        }
     

    }
    
    if(*(ret) == 10) //자리수가 바뀌는 경우
    {
        *ret = 1; //맨 앞은 1로 바꾸고
        *(ret+digitsSize) = 0; //NULL->0으로 바꾸어준다
        (*(returnSize))++;  //최종 자리수를 +1 한다.
    }

    
    return ret;
}

Mistake

1을 증가시키는 과정에서 (degit+i-1)++ 로만 둬 계속 오류가 발생했다.

(degit+i-1)++ 이거는 포인터 위치를 바꾸는 거고, (*(degit+i-1))++ 이렇게 해야 맞다.

그냥 degit[i-1]++ 이렇게 쓰도록하자.

New things learned

글을 쓰면서 느낀건, 코드가 너무 조잡하고 복잡한 것 같다. 

다시 풀어보도록 하겠다.

Identifying the Problem

띄어쓰기 뒤에 있는 문자열의 길이를 리턴한다.

제한조건 

• 1 <= s.length <= 10^4
• s consists of only English letters and spaces ' '

Organizing thoughts

0. 애초에 문자열 길이가 1인 경우는 결과가 두 개이기에 처리한다.

1. 문자열 길이만큼 반복한다.

2. 글자수를 count 하다

2-1 스페이스바를 만나면 count를 0으로 초기화한다.

--- 여기까지는 모든 test case를 만족했지만,

HELLO WORLD_ _ 처럼 맨 뒤에 띄어쓰기 두 개를 써리면 다 초기화되어버린다.

또한 A _ 를 해도 1을 RETURN 하는 것이 아니라 0을 리턴한다.

이 문제를 어떻게 해결해야 할까?

3. count 가 0으로 초기화되기 전에 예비로 count를 저장해두면 된다!

하지만 count 를 막 저장하는 것이 아니라, count가 0보다 클 때 저장해야 한다.

매 시도마다 count를 예비로 저장해두면 의미가 없기 때문이다.

Sourcecode

int lengthOfLastWord(char * s){

    int count = 0;
    int i=0;
    int n = strlen(s);
    int temp = 0;
    
    if(n==1)
    {
      if(*s==' ') return 0;
      else return 1;

    }

    
    
    
    while( i<n )
    {
      if( *(s+i)==' '  )
      {
          if(i==n-1) break;
          count=0;
      }
      else
          count++;
      
        
      if(count>0) temp=count;
        
     i++;
    }
    
    return temp;
}

Identifying the Problem

주어진 nums 배열에서 가장 큰 부분합을 찾아 return 한다.

제한조건

• 1 <= nums.length <= 3 * 10^4
• -105 <= nums[i] <= 105

Organizing thoughts

계단식으로 가능한 모든 sum을 구해 가장 큰 경우를 return 한다.

계단식이라 함은 

0번 ~ 1번 합

0번 ~ 2번 합

0번 ~ 3번 합 ...

n-1번 ~ n번 합 까지 다 구하는 것을 말한다.

Sourcecode

int maxSubArray(int* nums, int numsSize){
 

if(numsSize == 1) return *nums; //size가 1인경우 전체합과 부분합이 같으므로 그대로 return
    
    
int sum = 0;
int max = -100000; //제한 조건에 따라 가장 작은 max값을 -100000로 초기화하였다.
int max_f = -100000;
 
for(int i=0; i<numsSize; i++)
{
    
    
    
    for(int k=i; k<numsSize;k++)
    {
     sum+= *(nums+k);
     if(sum>max) max =sum; //i번째에서 가능한 최대 max 값을 찾아 max 에 넣는다.
         
    }
    
    if(max > max_f) max_f=max; //전체 중에서 가장 큰 max 값을 max_f 에 대입한다.
    
    sum = 0; //sum과 max을 초기화한다.
    max = -100000; 
}    
    
    
    return max_f;
}

Mistake

시간복잡도 O(n) 제한 조건을 어겼다.

분할 정복 알고리즘으로 다시 풀어보도록 하겠다. 

알고리즘 형태, 자료구조 등 배울 것이 태산이다. 

조건에 부합하지 않더라도, 최대한 스스로 풀 수 있는 방법에 집중할 것이다.

New things learned

Identifying the Problem

오름차순 정렬된 nums 수열안에 target이 들어갈 index를 return한다.

Organizing thoughts

1. 수열이 비어있는 경우 0을 return 한다.

2. target이 수열 내에서 가장 큰 경우 numsSize를 return 한다.

3. target이 nums의 다음 수보다 작거나 같으면 해당 index를 return한다.

Sourcecode

int searchInsert(int* nums, int numsSize, int target){
    
    if(numsSize == 0) return 0;
        
    for(int i=0; i<numsSize; i++)
    {
      if( target <= *(nums+i) )
         return i; 
    }
    
  return numsSize;
}

Identifying the Problem

haystack 문자열 안에 needle이 있으면 곂치는 부분의 첫 index를 return

곂치는 부분이 없다면 -1 return

Organizing thoughts

1. haystack 길이보다 needle이 긴 경우, haystack이 ""인 경우는 -1을 return 한다.

2. needle이 ""인 경우 0을 return 한다.

3. haystack 과 needle이 같은지 검사한다.

3-1 haystack과 needle의 첫 글자가 같은 경우

3-2 해당 부분부터 needle과 같은지 검사한다.

3-3 같은 부분의 수와 needle의 길이가 같다면

3-4 해당 index를 return 한다.

Sourcecode

int strStr(char * haystack, char * needle){
    
  int h_len = strlen(haystack);
  int n_len = strlen(needle);
  int index = -1;
  int count = 0;

  
if(n_len > 0 && h_len==0) return index; //1
else if(n_len>h_len) return index; //1
else if(n_len == 0 && h_len>=0) return 0; //2


    
for(int i=0; i<h_len-n_len+1; i++) //3
{   
    if(haystack[i] == needle[0]) //3-1
    { 
        
       
        
      for(int k=0 ; k<n_len;k++) //3-2
      {
      	 if(haystack[i+k] == needle[k])
            count++;
      }

    }
    
    if(count == n_len) //3-3
    {
        index = i;
        break;
    }
    count = 0;
}    

    
return index;
}

Identifying the Problem

주어진 수열들 중 val 값과 같은 경우 수열에서 제거한다.

제한조건

• 0 <= 문자열 길이 <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100
• 새로운 배열을 생성해서는 안된다.
• 시간 복잡도는 O(1) 이여야 한다.

Organizing thoughts

buble sort의 원리를 사용해서 val을 거르는 방식을 채택하였다.

Sourcecode

(1) 내가 작성한 코드지만, 시간복잡도 O(1)을 초과한다.

int removeElement(int* nums, int numsSize, int val){

    int count = 0;
    int temp = 0;
    
    
    if(numsSize == 0) return 0;
    if(numsSize == 1 && nums[0]  == val) return 0;
    
    for(int i =0 ; i<numsSize; i++)
        if(nums[i] == val)
            count++;
    
    if(count == 0) return numsSize;
    
    for(int i = 0; i<count;i++)
        for(int k=0; k<numsSize-i-1;k++)
            if(nums[k] == val)
            {
             temp = nums[k+1];
             nums[k+1] = nums[k];
             nums[k] = temp;


            }

    
    return numsSize - count;
    
    
    
}

(2) 아래는 다른 사람이 작성한 코드이다.

int removeElement(int* nums, int numsSize, int val) {
    int i, start = 0;
    for (i = 0; i < numsSize; i++) {
        if(nums[i] != val)
            nums[start++] = nums[i];
    }
    return start;
}

New things learned 

• 제한 조건이 O(1)인 경우 index의 역할을 두가지로 나누면 단순화가 가능하다.