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의 역할을 두가지로 나누면 단순화가 가능하다.

Identifying the Problem

주어진 수열 내에 존재하는 중복 요소들을 제거하고, 수열의 길이를 리턴한다.

제한 조건은 다음과 같다.

• 0 <= 수열의 길이 <= 3 * 10^4
• -100 <= 개별요소 값 <= 100
• 주어진 수열은 오름차순이다.
• 시간복잡도 O(1)이고, 다른 수열을 생성해선 안된다. 

Organizing thoughts

Main idea는 중복된 수가 있을 때 마다 pass하고,

비교하는 두 수가 서로 다를 때, 더 큰 수를 앞에 보내면 된다.

즉, 다음 수를 누적중복된 만큼 앞으로 보내면 된다. (아래에서 누적중복은 pass의 개수이다.)

다음과 같이 이해하면 쉬울 것 같다.

1. numSize 가 0,1 인 경우는 중복이 불가능하다.

2. 앞과 뒤를 비교하려면 size - 1 까지 해야한다.

3. 같을 경우 누적중복을 증가시키고,

4. 다를 경우 다음 수를 누적중복 앞만큼 보낸다. 

Sourcecode

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

      }
    }

    
    return count;
}

Mistake

처음에 중첩 반복문으로 작성했다가, 시간복잡도에서 벗어나서 컽 당했다.

도저히 모르겠어 로직을 참고했다.

New things learned

누적 중복 말고, 반복문 i 와 다른 속도로 가는 새로운 index 를 적용시키면 더 직관적일 것 같다.

Identifying the Problem

두 linked list 를 합치고, 오름차순 정렬하기

제한조건

• 한 노드의 길이는 50이고
• 노드안의 개별값은 -100 ~ 100 이다.
• 각 노드는 이미 오름차순 정렬 되어있는 상태이다.

Organizing thoughts

1. 둘 중 하나가 빈 노드라면, 반대 노드를 출력한다.

2. 정답 노드를 생성해 l1 , l2의 값을 비교하며 작은 것부터 채워 넣는다.

Sourcecode

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode answer;
    answer.next = NULL;
struct ListNode * ans = &answer;
    
if(l1 == 0) //1
    return l2;
else if (l2 ==0)
    return l1;

while(l1!=0 || l2!=0) //2 둘다 null이면 끝난거임
{
   if(l1->val <= l2->val )
   {
    ans->next = l1;
    l1 = l1->next;
   }
    else
   {
    ans->next = l2;
    l2 = l2->next;
   }
   
    ans = ans-> next;
    
    if(l1==0)
    {
     ans->next = l2;
     break;
    }
    
    else if(l2==0)
    {
     ans->next = l1;
     break;
    }
    
   
}
    
    
    
     
    
    return answer.next;
    
}

Mistake

없음

New things learned

이해가 안가면 그림을 그려보자

Identifying the Problem

주어진 단어들의 공통 접두사를 찾아 리턴한다.

Ex ) strs = ["flower","flow","flight"] -> output : fl

제한조건은 다음과 같다.

• 1 <= 단어의 개수 <= 200
• 0 <= 각 단어별 길이 <= 200
• 모든 strs[i] 는 소문자이다. 

Organizing thoughts

0. 단어가 하나이면 전체 return, 단어 중 " "이 있는 경우 return 0

1. 가장 짧은 단어의 길이를 구함

2. 그 길이만큼 반복하면서

0번째 1번째

1번째 2번째

2번째 3번째

... 비교하다가

서로 다른 경우가 있으면 바로 이전까지의 정답 return

Sourcecode

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

char * longestCommonPrefix(char ** strs, int strsSize){
 
    if (strsSize == 0) return ""; //0
    if (strsSize == 1) return strs[0]; //0
    
    char *answer = malloc(sizeof(char) * 200);
    strcpy(answer,"");
    
   
    int ss=0;
    int n[200] = {0,};
    
    ss= strlen(*strs);
    
    if(ss==0) return answer;  //0  
    
	for(int i=1;i<strsSize;i++) //1
	{
	    n[i] =strlen(strs[i]);
 	   if(ss>n[i])
 	   	ss = n[i];
    
	}    
    
         
	for(int i=0;i<ss;i++) //2
	{
  	 for(int k =0; k<strsSize-1 ; k++) 
 	  {
	   	if(strs[k][i] != strs[k+1][i])
	            	return answer;
   
   	}       
   
  	 strncat(answer,&(strs[0][i]),1);
	}     
    
    return answer;
}

Mistake

단어수가 3개인 줄 알고,

A=B, B=C -> A=C 논리를 써서 코드 작성했다가 단어 수가 3개 이상이 될 수 있었음을 늦게 알고,

갈아엎음.. 

New things learned

• strncat(answer,&(strs[0][i]),1) 에서 strcat 을 사용했으면 hello ello llo lo o 가 누적이 되었을 것이다. 
• strlen, strcat, strcpy 의 파라미터는 포인터 형으로 주어야 한다.
• 2차원 포인터 문자열을 사용할 때, s[j][k] 이런 식으로 하는 습관을 기르자
  굳이 하겠다면 *(*(ptr_ary+j)+k) 이런식으로 사용하면 된다.
• 문자열 포인터는 읽기 전용이기에 개별 요소를 변경하는 것은 불가능하다.
  *(str + 1) = 'z' (X)

Identifying the Problem

로마 숫자 표기를 int 형 숫자로 리턴하는 문제이다.

자세한 것은 아래 블로그를 참고하였다.

Organizing thoughts

핵심 아이디어는 로마자 숫자 표기는 4와 9를 표기할 때만 왼쪽에 I를 붙이는 것이다.

40, 90도 마찬가지 이다. 

따라서 4와 9인 case 와 아닌 경우로 나누어 조건을 분리하였다.

또한 문자별로 M > D > C > L > X > V > I 의 우선순위를 갖고, 

그렇기에 5단위는 10단위 앞에 올 수 없고, D앞에 C를 제외한 나머지는 들어갈 수 없다.

이러한 모든 조건을 따져 보면 조건이 그렇게 많지 않음을 알 수 있다.

따라서 이러한 조건을 짠 후, 문자열 길이만큼 반복문으로 검사하였다.

1. 변수 sum 0으로 생성 후 초기화

2. 문자열 길이 파악

3. 조건 작성

4. 조건에 따른 수 sum 에 누적 

Sourcecode

int romanToInt(char * s){
  int n = strlen(s);
  int answer = 0;
  char c=0,nxt = 0;
    
  for(int i=0;i<n;i++)
  {
    c = *(s+i);
    nxt = *(s+1+i);
    
    if(c=='M')
      answer += 1000;
    
    if(c=='D')
      answer += 500;
      
    if(c=='C')
    {
      if(nxt =='M' ||nxt =='D')
         answer -=100;
      else
         answer +=100;
     
    }
      
    if(c=='L')
         answer +=50;    
     
    if(c=='X')
    {
      if(nxt =='C' ||nxt =='L')
         answer -=10;
      else
         answer +=10;
    } 
      
    if(c=='V')
      answer += 5;
      
    if(c=='I')
    {
      if(nxt =='X' || nxt =='V')
         answer -=1;
      else
         answer +=1;
     
    }
     
  }
    
   
   
    
  return answer;
    
}

Mistake

어렵다고 생각할 수 있지만, 의외로 쉬운 경우가 많다.

New things learned

• 패턴을 찾으려기보다, 가능한 모든 경우를 파악하는게 더 좋을 수 있다.

가끔은 노가다가 정답일지도..??

Identifying the Problem

주어진 괄호 문자열이 올바르게 열고 닫혀야된다.

[ ) 같은 경우나, [ ( ] ) 경우는 false 값을 return 해야 한다.

Organizing thoughts

괄호가 양파를 속에서 까는 것 처럼 구상했다.

이를 위해 STACK 자료구조를 사용했다.

가장 깊은 괄호를 제거하다 보면 true 인지 false 인지 구분이 되기 때문이다.

예를 들자면, < ( [ ] ) > 에서 가장 깊은 괄호는 [] 이고

1 step 에서 []를 제거하면 <()>

2 step 에서 ()를 제거하면 <>

3 step 에서 <>을 제거하면 아무것도 남지 않는다.

1. 애초에 true가 되지 않는 경우

1-1 괄호가 아예 없거나

1-2 문자열의 길이가 홀수인 경우이다.

2. 나머지의 경우는 짝수의 경우이다.

2-1 stack에 문자열을 하나씩 집어넣다가

2-2 짝이 맞는 괄호가 있으면 마지막괄호와 들어온 괄호를 제거하고

2-2-1 아스키코드를 활용해서 두 괄호 값의 차가 일정값이면 짝이 맞는 것이다.

2-3 index를 마지막 괄호 이전으로 놓는다.

3. stack에 뭐가 남아있으면 fasle, 다 지워졌으면 true 를 return 한다.

Sourcecode

bool isValid(char * s)
{
	int n = strlen(s); 
	int t = 1; //스택의 index
	char stack[10000] ={0,}; //스택
	int gap=0;

	if(n==0) return true; //1-1
	else if(n%2 ==1) return false; //1-2
	
   	 else //2
             {
  	 	for(int i=0; i<n; i++)
        		{
   			stack[t] = *(s+i); //2-1
    			gap = stack[t] - stack[t-1];
    		
			if( 0<gap && gap<3   &&i>0) //[]같은 경우 gap 값이 2가 된다.
   	 		{
    				stack[t]=0; //2-2
   	  			stack[t-1]=0;
     				t= t-2; //2-3
  			}
            
  			t++;
 	 	}
	}
    
    
    if(stack[1] == 0) return true;
    else return false;
}

Mistake

모든 경우의 수를 생각하며 패턴을 찾는 데에 집중했다.

바로 옆과 끝의 관계에 따라 코드를 짜봤는데 너무 복잡하고, test case 에서 걸러지는 경우 더 코드가 복잡해졌다.

어떻게든 혼자서 풀려고 노력했는데 도저히 생각이 안나 solution을 참고했고, 의외로 단순한 문제였다.

도저히 안풀리는 것은 solution과 다른 사람의 코드를 보고 빨리 진행하는 것이 좋을 듯 하다.

New things learned

• Stack 자료구조 Last In First Out 구조로 프링글스 통안에 자료를 집어넣고 뺀다고 생각하면 된다.

Identifying the Problem

가운데 숫자를 중심으로 양끝의 숫자가 대칭을 이루는지 확인하는 문제

예를 들면 121 같은 경우 2를 기준으로 1이 대칭을 이루지만 123 같은 경우는 그렇지 않다.

단 음수일 경우 false 를 return 한다.

제한조건은 다음과 같다.

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

Organizing thoughts

7번 문제 (숫자 뒤집어서 리턴) 하는 문제에서 x와 answer 과 똑같은지 판단해서 푸는 방법도 생각해봤지만

코드가 너무 복잡한 관계로 배열을 사용해 푸는 방법을 mainidea로 채택했다.

<Main idea>

음수일 경우 리턴하고, 정수를 배열 형태로 쪼개고 처음과 끝을 비교하는 방식이다.

0. 제한조건에 따른 x값의 최대 자리수는 12자리이므로 크기가 12인 배열을 선언한다.

1. 모든 자리수의 숫자를 추출 후 배열에 입력한다.

1-1 자리수를 파악한다.

1-2 숫자를 추출하고, 자리 수를 파악한다.

2. 양끝을 비교한다. 홀수 짝수 상관없이 n/2 번 반복하면 된다. (정수형에서 5/2 = 2)

2-1 비교 시 다를 경우 flag에 1을 대입한다.

Sourcecode

bool isPalindrome(int x){
    int num[12] = {0,};
    long long int n=0,temp=x; //n은 자릿수, temp는 자릿수 구할 때 사용할 x 값 
    bool flag = true; //다를 경우를 판단할 flag 
    
    long long int X = x; //제한 조건에 맞게 long long int 를 사용함
	
    if(x<0) flag = false; //음수는 입구 컷!
	
    else if (x>9) // 한 자리수는 무조건 true를 return 하게끔
	{
    
    
    	while(temp !=0)
    	{
        	num[n] = temp%10; //1-1번
        	temp /=10; //1-2번
        	n++;
        	

	    }
    
    	for(int i=0; i<n/2; i++) //2번
    	{
     		if(num[i] != num[n-1-i]) //2-1번
        		flag = false;
    	}
        
	}   
    
    return flag;
}

Mistake

없음

New things learned

• 많은 test case 들이 있어 처음 생각을 정리하는 과정에서 가능한 모든 경우의 수를 생각하고
  코딩하는 과정이 중요한 것 같다.

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 적어가서 최대한 고민해보는 시간을 가져보도록 하겠다.

글 양식은 

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

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

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

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

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

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

파이팅!

스무 살인 지금 살아가면서 처음으로 대공황을 겪었다. 

물론, 내가 태어난 2001년도 IT버블과 2008년도 리만브라더스 사태는 무슨 일이었는지 당시에는 알지 못했다.

COVID-19로 3월 대공황이 시작한 이후, 모두가 눈에 불을 켜고 주식시장에 발을 들일 때,

나도 덩달아 뛰어들기 시작했다.

정말 아무 생각 없이 뛰어들었다. 삼성전자만 사도 대박이 났고, 주어 들은 현대차는 12만 원에서 2주 사이에 17만 원으로 폭발하기 시작했다. 

미친 듯이 공부하다 보니, 한국 주식시장은 일종의 투기장이었다. 

동학 개미 운동이라는 멋있는 포장 아래 '코스닥'의 종목은 +30% ~ -30%를 오갔다.

코스피 하위종목들도 마찬가지이다.

-2~30% 이후에는 상승여력을 잃어 횡보에 그치게 된다.

원금 복구에는 엄청난 시간적 손실과 오랜 스트레스를 이겨내야한다.  

또한 실시간 검색어에 대부분이 주식 종목 명인 것이 크나큰 충격이었다.

주변 사람들도 PER가 어떠냐느니, 차트가 어떠냐느니 떠들기 바빴다.

하지만 아무리 차트 분석을 해도, 다음날 악재가 나오면 -10%는 기본이었다.

대다수의 주식들이 엿 모양을 그리며, 세게 한 대 맞은 이후 복구되기 힘들어 보였다.

그야말로 국내 주식은 갈대처럼 힘이 없었다.

차트도 아니고, 재무제표 분석도 아니었다. 

모든 것의 근간은 Fundamental과 Story 였다.

그리고 무너지더라도 강한 상승 모멘텀을 가지고 일어서는 곳을 찾아 헤맸다.

결과는 미국 주식이었다.

그 중에서도 NASDAQ-100은 4차 산업혁명의 선두주자로 나서고 있고,

더욱 폭발할 것이라는 믿음을 가지게 되었다. 

불과 10년사이에 6배가량 성장했음을 볼 수 있다. 

중간마다 경제 대공황과 Recession으로 상승세가 꺾인 부분들이 있지만,

이는 더 큰 상승 모멘텀으로 작용하였다.

IT Tech 버블처럼 4차산업혁명 Tech 버블은 머지않아 도래할 것이다.

애플, AMD, QCOM, TSLA, 마이크로소프트의 나스닥 선두주자는 이를 이끌어 낼 것이고,

지금 글을 읽고 있는 이 순간이 그 시작점이다.