Identifying the Problem

주어진 수열에서 세 숫자의 합이 0이 되는 경우를 찾아 해당 경우를 배열로 리턴한다.

단, 중복되는 경우는 제외한다.

Organizing thoughts

O(n³)으로 모든 경우를 찾는 방법도 있지만 비효율적이다.

MAIN IDEA는 오름차순정렬 후 탐색 값을 고정하고,

그 다음값과 맨 끝값을 가운데로 조여가면서 세 수의 합이 0인 경우를 찾는다.

위와 같을 때 탐색 값이 -4일 때 왼쪽을 탐색 값의 다음 값인 -1 오른쪽을 맨 끝 값인 2로 설정한다.

만약 세 수의 합이 0보다 크다면, 합을 줄여야 하므로 오른쪽 index를 줄인다.

만약 세 수의 합이 0보다 작다면, 합을 늘려야 하므로 왼쪽 index를 늘린다.

만약 세 수의 합이 0과 같다면, 정답 배열에 입력한다.

여기까지는 완벽하다.

그렇다면, 중복이 되는 조건은 어떻게 처리해야 할까?

중복이 되는 경우는 크게 두가지가 있다.

첫째는 합이 0일 때, left와 left의 다음 값이 같거나, right 와 right 이전 값이 같은 경우가 있다.

이는 각각의 이전 혹은 다음값과 다를 때까지 가운데로 index를 옮겨주면 된다.

둘째는 탐색하는 index가 이전과 같은 경우이다.

예를 들어 위의 배열에서 탐색 값이 nums[1] 일 때와 nums[2] 때 [-1,0,1] 이 정답 배열에 두번 생긴다.

이 같은 경우는 nums[2]일 때, 합을 구하는 과정을 생략하면 된다.

Sourcecode

#include<stdlib.h>

int compare(const void *one,const void *two){
	if(*(int *)one>*(int *)two)
		return 1;
	else if(*(int *)one<*(int*)two)
		return -1;
	else return 0;
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){

    qsort(nums, numsSize, sizeof(int), compare); //오름차순 정렬
    
    int** ans = malloc(sizeof(int) * (numsSize) * (numsSize)); //정답 배열
    *returnSize = 0;
    int left, right, sum;
      
    for(int i=0; i<numsSize-2; i++)
    {

        left = i+1;
        right = numsSize - 1;
        
        if(i>0 && nums[i] == nums[i-1]) continue; 
        //탐색값이 이전과 같으면, 합 구하는 과정 생략
        
        
        while(left < right)
        {
            sum = nums[i] + nums[left] + nums[right];
            
            if(sum >0) right--;
            else if(sum<0) left++;
            else
            {
                ans[*returnSize] = malloc(sizeof(int) * 3); //정답배열에 추가
                
                ans[*returnSize][0] = nums[i]; 
                ans[*returnSize][1] = nums[left];
                ans[*returnSize][2] = nums[right];
                
                right--; left++;
                
                while(left < right && nums[right] == nums[right+1]) right--;
                while(left < right && nums[left] == nums[left-1]) left++;    
                //0인 경우 중복되는 경우 없애기
                
                (*returnSize)++;
            }   
        }
    }
    
    *returnColumnSizes = (int*)malloc(sizeof(int)*(*returnSize));
    for (int i = 0; i < *returnSize; i++)
        (*returnColumnSizes)[i] = 3;
    
    return ans;
}

Mistake

42번, 43번줄에서 left < right 를 해주지 않게 되면, left나 right가 지정된 메모리 범위를 벗어나는 경우가 생긴다.

Identifying the Problem

matrix 중 0이 있다면 해당 0의 행과 열을 모두 0으로 바꾼다.

Organizing thoughts

MAIN IDEA : 0이 있는 행, 열의 위치를 저장해두었다가, 저장된 위치를 모두 0으로 바꾼다.

1. matrix 전체를 탐색하며 0이 있는 경우

2. 0의 행 index와 열 index를 저장

3. 행 또는 열의 길이만큼 탐색하며, 저장된 index에 해당하는 행과 열을 모두 0으로 바꾸어 준다.  

Sourcecode

void setZeroes(int** matrix, int matrixSize, int* matrixColSize)
{
    int* cols = (int*) calloc(*matrixColSize, sizeof(int)); //열의 index를 저장할 배열
    int* rows = (int*) calloc(matrixSize, sizeof(int)); //행의 index를 저장할 배열
    
    
    
    for(int i = 0 ; i<matrixSize; i++) // 1과정
    {
        for(int k = 0 ; k<*matrixColSize; k++)
        {
           
            if(matrix[i][k] == 0) // 2과정
            {
                rows[i] = 1; //1은 해당 위치에 0이 있다는 표시
                cols[k] = 1;
                
            }
        }
    } //0이 있는 행과 열 조사
   
    
    for(int i = 0 ; i<matrixSize; i++) // 3과정
    {
        
        if(rows[i] == 1)
        {
            for(int j = 0; j< *matrixColSize; j++)
                matrix[i][j] = 0;
        }
        
    } //조사한 행에 0이 있었다면, 해당 행을 모두 0으로 초기화
    
    for(int i = 0 ; i< *matrixColSize; i++) // 3과정
    {
        if(cols[i] == 1)
        {
            for(int j = 0; j< matrixSize; j++)
                matrix[j][i] = 0;
        }
        
    } //조사한 열에 0이 있었다면, 해당 열을 모두 0으로 초기화
}

New things learned

malloc은 int* arr = malloc(sizeof(int) * n) 이런 식으로 사용했지만,

calloc은 arr = (int*) calloc(5, sizeof(int)) 이런 식으로 써야 한다.

Identifying the Problem

주어진 mxn 2차원 행렬을 나선형으로 탐색하며

1차원 배열에 값을 저장해 리턴한다.

Organizing thoughts

MAIN IDEA : matrix를 탐색하는 좌표를 방향키로 조정하듯 조절한다.

그림을 보면 간단한 규칙을 알 수 있는데,

[1]

<행 오른쪽  위 도달 시> 방향은 아래로 바뀜

<행 오른쪽 아래 도달시> 방향은 왼쪽으로 바뀜

<행 왼쪽   아래 도달시> 방향은 위로 바뀜

<행 왼쪽   위 도달시> 방향은 오른쪽으로 바뀜

[2]

한번 끝에 도달하면, 끝의 index는 가운데 쪽으로 한 칸 움직인다.

Sourcecode

int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize)
{
    int* ans = malloc(sizeof(int)* *matrixColSize * matrixSize); //정답 array
    int i = 0; //정답 array index
    int up = 0; //윗 방향
    int down = 0; //아랫 방향
    int left = 0; //왼쪽 방향
    int right = 0; //오른쪽 방향
    
    int x = 0; //matrix x좌표
    int y = 0; //matrix y좌표
    
    int left_end = 0; //왼쪽 끝 index
    int right_end = * matrixColSize - 1; //오른쪽 끝 index
    int up_end = 0; //위쪽 끝 index
    int bottom_end = matrixSize - 1; //아래쪽 끝 index
    
    right = 1;
    
    if(*matrixColSize == 1 || matrixSize == 1) 
    {
        if(*matrixColSize == 1){right = 0; down = 1;}
         
        up_end--;
        bottom_end ++;
        left_end--;
        right_end++;
    }
    
  
    while(i < *matrixColSize * matrixSize)
    {       
        ans[i] = matrix[y][x];
        
        if(left == 1) x--;
        else if(right == 1) x++;
        else if(up == 1) y--;
        else if(down == 1) y++;
        
        if(x==left_end && y>up_end) //왼쪽 아래 끝 일때
        {
            left = 0; 
            up=1; 
            left_end++;
            
        }
        else if(x==right_end && y<bottom_end) //오른쪽 위 끝 일때
        {
            right = 0;
            down = 1;
            right_end--;
        }
        else if(y==up_end && x<right_end) //왼쪽 위
        {
            up = 0;
            right = 1;
            up_end++;
        }
        else if(y==bottom_end && x>left_end ) //오른쪽 아래 끝
        {
            down = 0;
            left = 1;
            bottom_end--;
        }
        
        if(bottom_end < up_end) bottom_end = -1; 
        
        i++;
    }
    *returnSize = i;
    
    
    return ans;
}

Mistake

• 행이나 열이 1줄인 경우를 생각 못했다.
• 66번줄의  if(bottom_end < up_end) bottom_end = -1는
  bottom_end 값이 up_end 보다 커지는 순간이 발생하는데, 이는 행이 홀수개인 경우 생기며,
  탐색하는 값이 오른쪽 아래 끝에 위치해 있다고 판단하게 된다.
  이 부분을 막기 위해, bottom_end를 -1로 바꿔 오른쪽 아래 끝 조건문에 걸리지 않게 했다. 

Identifying the Problem

주어진 수열에서 가장 긴 오름차순 부분 배열의 크기를 구한다.

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: 가장 긴 부분 배열의 길이는 [2,3,7,101] 이므로 길이는 4이다.

Organizing thoughts

핵심 IDEA는 수열을 탐색하면서 해당 index에서 가능한 가장 큰 배열에 길이를 따로 저장해 두는 것이다.

즉 이전 수들 중에서 다음 수로 증가했을 때, 이전 수들 중에서 가능한 가장 큰 배열 길이 + 1을 하는 것이다. 

초기 첫번째는 count가 무조건 1이 된다.

nums = [10,9,2,5,3,7,101,18] 이라면

count = [1,1,1,2,2,3,4,3] 이 되고, 여기서 가장 큰 max 값만 따로 정답으로 내면 된다.

더 깊게 설명하자면,

5를 탐색할 때 5 이전 5보다 작은 값은 [2]이고, 2의 count값 + 1 한 것이 count[3] 이 된다.

7을 탐색할 때 7 이전 7보다 작은 값은 [2,5,3]이고

각각의 count값은 [1,2,2] 가 되고, count 값의 최고 값 2 + 1 한 것이 count[5] 가 된다.  

Sourcecode

int find_max(int* c, int n) //수열에서 가장 큰 값을 찾는 함수
{
    int max = 0;
    for(int i = 0; i<n ; i++)
    {
        max = max<= c[i] ?  c[i] : max;
    }
    
    return max;
}

int f_max(int a, int b) //max 함수
{
    if (a>b) return a;
    else return b;
}

int lengthOfLIS(int* nums, int numsSize)
{
    if(numsSize < 2) return numsSize; //nums 길이가 0,1인 경우 답은 0,1이다.
    
    int* count = malloc(sizeof(int) * (numsSize)); //count 배열 생성

    count[0] = 1; //count[0]은 무조건 1이다.
    int max = 1; //비교용 max 
    			//count[0]이 1이므로 초기값은 1로 시작
    
    for(int i = 1; i< numsSize; i++)
    {
        count[i] = 1; //이전에서 다음으로 증가하지 않는 경우도 있기에 
        			  //count의 모든 초기값은 1로 대입
        
        for(int k = 0; k<i ; k++)
        {
            if(nums[i] > nums[k])  //수가 증가했다면 가능한 max의 값을 찾는다.
            {   
            	max = f_max(max,count[k]); 
                count[i] = max+1;
            }
        }
        max = 1; //i가 넘어가므로 max를 초기화 시켜준다.
    }

    return find_max(count, numsSize);
}

Mistake

• max를 초기화시키는 과정을 생략했다.

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

강도가 집을 털 때 가장 많이 훔칠 수 있는 경우를 구한다.

단, 바로 옆집으로 갈 경우 들키므로 바로 한 집과 바로 옆집을 털지 못한다. 

Organizing thoughts

홀수칸 털었을 때랑 짝수칸 털었을 때 비교해서

최대값 구하면 되는 거아닐까? 라는 생각을 했다.

이 경우 [2,1,1,2]를 설명할 수 없다.

생각해본 결과 단순한 규칙을 찾을 수 있었는데,

처음 집의 최대(problem)를 구하려면 다음 집, 그 다음 집의 최대(sub-problem)를 알아야 구할 수 있다.

Dynamic Programing으로 접근 가능하다.

끝 index부터 처음 index까지 최대값을 구하고 최종적으로

처음 index의 최대값을 리턴하면 된다. 

sum = 해당 인덱스에서 가능한 최대 값이다.

nums = [8,2,3,20,10,8,5]  같은 경우 패턴을 구하면,

sum[6] = 5

sum[5] = 8 과 sum[6] 중 큰 값

여기까지는 패턴이 존재하지 않으므로, 초기값으로 설정하고,

sum[4]  = 10 + sum[6] 과 sum[5] 중 큰 값 

sum[3] = 20 + sum[5] 과 sum[4] 중 큰 값 

sum[2] = 3 + sum[4] 과 sum [3] 중 큰 값

sum[1] = 2 + sum[3] 과 sum[2] 중 큰 값

sum[0] = 8 + sum[2] 과 sum[1] 중 큰 값

이후로는 패턴이 나타나기 시작한다.

Sourcecode

int rob(int* nums, int numsSize)
{
	int* sum = malloc(sizeof(int) * numsSize);
	
	if(numsSize  == 0) return 0;
	else if(numsSize  == 1) return nums[0];
	else if (numsSize  == 2) return nums[0] > nums[1] ? nums[0] : nums[1]; 

	sum[numsSize - 1] = nums[numsSize - 1];
	sum[numsSize - 2] = nums[numsSize - 2] > nums[numsSize - 1] ? 	nums[numsSize - 2] : nums[numsSize - 1];

	
	for(int i = numsSize-3; i>=0;i--)
	{
		sum[i] = nums[i] + sum[i+2] > sum[i+1] ? nums[i] + sum[i+2] > sum[i+1];
	}

	return sum[0];
}

Identifying the Problem

주어진 nums로 target을 만들 수 있는 가능한 경우의 수를 구한다.

Organizing thoughts

주어진 nums로 target 이전의 수를 만들 수 있는 경우를 다 구하고

target에서 각 nums를 뺏을 때 해당 경우의 수 값을 다 더해주면

target을 만드는 경우의 수가 된다. 

problem 은 target 의 가능한 경우의 수를 구하는 것이고,

sub-problem은 target 이전의 가능한 경우의 수를 미리 구해

target에 2,3,5를 뺏을 경우 각각의 가능한 경우의 수를 더함으로 답을 구한다.

Ex ) nums = [2,3,5]
target 12 라면

12에서 2,3,5를 뺀 10,9,5를 만들 수 있는 경우의 수
10-(2,3,5) 9 - (2,3,5) 5 - (2,3,5)... top-down 방식으로 생각했다면
1,2,3,4,5,6.... target의 값을 구해 bottom-up 방식으로 답을 구하면 된다.

Sourcecode

int combinationSum4(int* nums, int numsSize, int target)
{
    size_t combination_sum[1000] = {1, 0, 0};
    
    for (int i = 1; i <= target; i++) //target 이전까지의 count들을 미리 구하면됨
    {
        for (int j = 0; j < numsSize; j++)
        {
		if(0<=  i - nums[j])
            		combination_sum[i] +=  combination_sum[i - nums[j]]; 

		else 
			combination_sum[i] += 0; //index가 음수가 되는 경우 아무 것도 하지 않는다.
        }
    }
    
    return combination_sum[target];
}

New things learned

dynamic problem은

problem을 풀기 위해, sub-problem을 미리 풀어놓음으로, problem을 해결한다.

이 문제 같은 경우 dynamic problem의 중요한 부분은

예측 가능한 초기값을 설정해 두는 것인데,

주어진 nums로 0을 만드는 경우의 수는 1로 설정했다. 

(아무것도 안 더하는 게 하나의 경우의 수로 본다.)

Identifying the Problem

다수의 linked list를 하나로 연결하고, 오름차순 정렬한다.

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] 

Organizing thoughts

1. listsSize -1 번 만큼 반복하며, list를 연결시킨다.

2. 하나로 연결시킨 linked list를 오름차순 정렬한다. 

Sourcecode

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{

    int i = 0;
    int j = 0;    
    int k = 0;
    int count = 0;
    int swap_num;

    if(listsSize == 0) return NULL; //아무것도 없는 경우 NULL 

    struct ListNode* swap; //버블 정렬용 포인터
    
    for(int i=0 ; i<listsSize-1; i++) //버블sort를 사용해 NULL포인터를 다 뒤로 밀어버린다.
    {
        for(int j=0; j<listsSize-1-i;j++)
        {   
            if(lists[j] == NULL)
            {
                swap = lists[j];
                lists[j] = lists[j+1];
                lists[j+1] = swap;
            }
        }
    }
    
    struct ListNode* tmp = lists[0];
    struct ListNode* ans = lists[0];


    while(tmp) //listSize만큼의 노드를 하나로 연결시킨다.
    {
        if(tmp->next == NULL && i < listsSize-1)
            tmp->next = lists[++i];

        tmp = tmp->next;
        count++; //count는 val이 들어있는 노드의 총 개수
    }



    while(k < count-1) //linked list 오름차순 버블정렬
    {
        struct ListNode* tmp = lists[0];

        while(tmp->next)
        {
            if(tmp->val > tmp->next->val)
            {
                swap_num = tmp->val;
                tmp->val = tmp->next->val;
                tmp->next->val = swap_num;
            }
            tmp = tmp->next;
        }

        k++;
    }
    
    return ans;
}

Mistake

testcase : [[],[-1,5,11],[],[6,10]] 같은 경우
NULL이 중간중간 껴 있어서, 연결이 불완전하게 되는 경우가 생겼다.
이 부분을 놓쳤다.

Identifying the Problem

주어진 linked list를 규칙에 맞게 재 정렬한다.
list가 L0 → L1 → … → Ln - 1 → Ln 순이라면
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 순으로 재 정렬

Organizing thoughts

MAIN :  메인은 중간까지는 정순, 중간 이후부터 list를 뒤집고,

            이후 왼쪽과 오른쪽 끝에서 중간으로 규칙대로 연결한다.

1. list의 가운데 주소 찾기 

    1.0 가운데의 next는 NULL이 되어야 한다.
2. 가운데 주소 이후부터 가운데 주소 다음까지 뒤집기
3. 양끝의 주소를 알아내고
4. 양끝부터 연결 시작

   4.0 1번 주소 저장
   4.1 0번과 n번 연결
   4.2 n-1번 주소 저장
   4.3 n번과 1번 연결
   4.4 2번 주소 저장

   …. 이런 식으로 계속

Sourcecode

struct ListNode* find_mid(struct ListNode* node);
struct ListNode* reverse(struct ListNode* node); 

void reorderList(struct ListNode * head)
{	
    struct ListNode* left = head; //왼쪽
	struct ListNode* mid = find_mid(head); //중간	
	struct ListNode* right = reverse(mid); //중간부터 끝까지 배열을 뒤집는다.
    
    mid->next = NULL;
    
    struct ListNode* left_tmp = head;
	struct ListNode* right_tmp = right;
    
    while(!(left == mid && right == mid))	
    {		
        left_tmp = left;		
        left = left->next; 		
        left_tmp->next = right;
        
        
		right_tmp = right;		
        right = right->next;	 		
        if(right==NULL) break; 
        //list가 짝수 개인 경우 마지막 반복에서 무한순회가 나게끔 고리가 형성된다.
        //이러한 오류를 막기위해 해당 조건문을 작성했다.
        right_tmp->next = left;	
    }
	
 }

struct ListNode* find_mid(struct ListNode* node)
{
	struct ListNode* fast = node;
	struct ListNode* slow = node;

	while( !(fast == NULL || fast->next == NULL))	
    {	
        
        fast = fast->next->next;		
        slow = slow->next;
	}		
    
    return slow;
}
struct ListNode* reverse(struct ListNode* node)
{
	struct ListNode* newHead = NULL;	
    
    while(node)	
    {
		struct ListNode* tmpNode = node -> next;		
        node->next = newHead;		
        newHead = node;		
        node = tmpNode;	
	}

	return newHead;
}

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

스택 생성하고, 스택을 다루는 함수를 만든다.

Sourcecode

typedef struct {
    int str[30000];
    int top; //stack의 끝 부분
    
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate()  //stack obj 생성
{
    
    MinStack *stack;
    stack = (MinStack*)malloc(sizeof(MinStack));
    stack->top=-1;
    
    return stack;
}


void minStackPush(MinStack* obj, int val) //stack에 요소 넣기
{
    (obj->top)++;
    obj->str[obj->top] = val;
    
}

void minStackPop(MinStack* obj) //꼭대기 요소 제거
{
    obj->str[obj->top] = NULL;
    (obj->top)--;
}

int minStackTop(MinStack* obj) //꼭대기 요소값 리턴 
{ 
    return obj->str[obj->top];
}

int minStackGetMin(MinStack* obj) // stack 내의 가장 작은 값 리턴
{
    int min = obj->str[0];
    
    for(int i=1;i<=obj->top;i++)
        if(obj->str[i] < min) min = obj->str[i];
        
    return min;
}

void minStackFree(MinStack* obj) { //obj의 동적할당 해제
    free(obj);    
}

Identifying the Problem

주어진 linked list가 무한 순회하는지 판단한다.

Organizing thoughts

 
<정답 참조했음>

비유를하자면 제논의 역설과 비슷하다.
운동장을 육상선수와 내가 돌고, 육상선수가 나보다 2배 빠르다고 했을 때, 
둘이 언젠가 만나는 지점이 있음

이 문제에선 그 지점을 찾으면 된다.

Sourcecode

bool hasCycle(struct ListNode *head) {
    
    struct ListNode *slow, *fast;
    
      
    
    if(!head || !(head->next)) //노드의 수가 1개 이하인 경우 false 리턴
        return false;
        
    slow = head->next; //2번째 노드
    fast = head->next->next; //3번째 노드
    
    while(fast && fast->next)
    {
       if(slow == fast) return true; //처음과 끝이 같아지는 지점
        
       slow = slow->next; 
       fast = fast->next->next; //slow의 2배속도로 탐색한다. 
    
            
    }
    
     return false;
}

New things learned

• 하나의 배열에 탐색 index를 여럿두면 배열 여러 개를 복사한 효과를 낸다.

Identifying the Problem

중복되는 수가 여럿 있는 수열에서 중복이 없는 수 하나를 찾아 리턴한다.

Organizing thoughts

시간 복잡도가 O(n²)인 방법으로 풀어보았다.

1. n^2 번 훑기
    단 1-1 자기가 자기 자신을 검사하면 안 된다.
2. 같을 시 flag = 1
3. <만약 flag 가 0으로 유지 시> 해당 index의 값을 return
4. 한 cycle 돌고 flag 0으로 초기화

Sourcecode

int singleNumber(int* nums, int numsSize){

    int flag = 0;
    int ans = 0;
        
    for(int i=0; i<numsSize;i++)
    {
        for(int k=0; k<numsSize;k++)
        {
            if(nums[i] == nums[k] && i!=k)
                flag =1;
        }
        
        if(flag == 0) ans = nums[i];
        
        flag = 0;
    }
    
    
    return ans;
}

Identifying the Problem

주어진 문자열이 가운데를 기준으로 대칭인지 확인한다.

Organizing thoughts

1. 특수문자 거르고 대문자는 소문자로 바꿔준다.
   1-1 크기가 기존 문자열과 같은 새로운 비교 문자열을 생성 
   1-2 기존문자열의 길이만큼 반복하면서 비교문자열에 특수문자 거르기
   1-3 아스키 코드에 들어오면 비교 문자열에 추가하고 비교 문자열 index값 증가

2. 거른 문자열이 palindrome 인지 파악
   2-1 다른경우 발견 시 return false

3. return true

Sourcecode

bool isPalindrome(char * s){
    int len = strlen(s);
    int index = 0;
    char arr[200000] = {0};
    
    
    for(int i=0; i<len;i++) //새로운 비교 문자열 생성
    {
        if('a' <= s[i] && s[i]<='z' || 48 <= s[i] && s[i]<= 57) //특수문자는 거른다.
            arr[index++] = s[i];
        
        else if('A' <= s[i] && s[i]<='Z') //대문자일 경우 소문자로 변환
            arr[index++] = s[i]-'A'+'a';   
        
        
    }
    
    
    for(int i=0; i<index/2;i++) //Palindrome인지 확인
        if(arr[i] != arr[index-1-i]) return false;
   
    return true;
}

Mistake

• char arr[size] 하면 에러남 왜 그런지는 모르겠다.
• strcat(arr, char* s[i] 를 해버리면) s[i] 뒤의 모든 문자열이 들어가므로, strncat(",",1) 을 해야된다.

Identifying the Problem

주식 price 수열 내에서 가장 큰 수익을 구한다.

price의 index는 증가는 시간 증가이다.

가장 쌀 때 사서 가장 비쌀 때 팔았을 때 이익을 구하는 문제이다.

Organizing thoughts

즉 profit은 0보다 커야하고, profit는 sell-buy 가 max 인 값이다.
그리고 마지막날에 산건 의미가 없다.

핵심 idea 는 한 arr을 탐색하는 인덱스를 선발과 후발로 나누면 한 arr가 2개로 복사되는 효과를 본다.
선발로 price[i]을 설정해 일반적으로 탐색하고,

후발은 min으로 가장 쌀 때의 가격을 저장해둔다.

따라서 price[i] 와 min의 차이를 profit으로 정하고, profit이 max인 경우를 리턴하면 된다.

Sourcecode

int maxProfit(int* prices, int pricesSize)
{
    
    int i = 0;
    int profit =0;
    int max=0;
    int min=prices[i];  
    
    
    
    for(i=1; i<pricesSize; i++)
    {   
        if(min > prices[i]) 
        	min = prices[i];
        
        else
        {
      		profit = prices[i]-min;
       		if(profit > max) max = profit;
        }
        
    }
        
    return max;
}

Identifying the Problem

row 층 까지 파스칼 삼각형을 만들어 리턴한다.

Organizing thoughts

파스칼 삼각형의 규칙은 간단하다.

• 양 끝은 항상 1로 끝나고
• 그 사이의 값들은 이전 층의 0번째 + 1번째 ... n-1번째 + n번째의 합으로 이뤄진다.
  단 이 규칙은 row가 3 이상일 때부터 적용된다.

Sourcecode

int** generate(int numRows, int* returnSize, int** returnColumnSizes){

    int** arr; //정답 어레이를 선언
    arr = (int**) malloc ( sizeof(int*) * numRows ); //행 배열 동적할당
    
    for(int i=0; i<numRows; i++)
    {
        arr[i] = (int*) malloc ( sizeof(int) * (i+1) ); //열 동적할당
        arr[i][0] = 1; //양 끝은 1
        arr[i][i] = 1;
    }   
    
    *returnSize = numRows;   //13 ~ 18줄은 test assert용
    *returnColumnSizes = (int*) malloc (sizeof(int) * numRows);
    
    
    for(int i = 0; i<numRows; i++)
        (*returnColumnSizes)[i] = i+1;
    
    int k=2; //row가 3 이상일때부터
    
    while(numRows>2 && k<numRows)
    {
         for(int i=1;i<k ;i++)
            arr[k][i] = arr[k-1][i-1] + arr[k-1][i]; 
            //이전층의 이전 index 와 현재 index를 합한다.
    

         k++; //다음 층으로 이동
    }



    
 return arr;
}

Identifying the Problem

주어진 수열에 중복이 있으면 true 없다면 false를 리턴한다.

Organizing thoughts

1. 퀵 정렬로 정렬 후

2. 중복이 있는지 검사하였다.

Sourcecode

#include <stdlib.h>    

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

bool containsDuplicate(int* nums, int numsSize){

    qsort(nums, numsSize, sizeof(int), cmp);
    
    for(int i = 0; i<numsSize-1;i++)
        if(nums[i] == nums[i+1]) return true;
    return false;
}

Identifying the Problem

음이 아닌 정수 a1, a2, ..., a가 각각 좌표(i, ai)의 한 점을 나타내는 경우

x축과 함께 용기에 물이 가장 많이 들어 있는 두 개의 선을 찾아 넓이를 구한다.

Organizing thoughts

O(n²) 으로 가능한 모든 넓이를 구해서 풀 수 있지만, 매우 비효율적이다.

간단한 원칙 두가지만 알면 이해하기 쉽다.

1. 가장 작은 기둥기준으로 넓이가 구해진다는 것

2. 가로길이는 조절 수 있지만 세로 길이는 상수값이기에 정할 수 없다는 것

즉 가로길이를 조절하면서 가장 큰 넓이를 구하면 된다.

길이가 n이고 가로길이가 n-1일 때 넓이를 구하는 방식은 2가지다.

만약 왼쪽 세로가 오른쪽 보다 더 길다면, 오른쪽의 가로길이만 줄이면 된다.

이런 식으로 왼쪽 오른쪽 비교해가면서 가로길이를 줄여나가며 최대 넓이를 구하면 된다.

처음 바로 이 생각을 하기에 너무 어렵다고 느낀다. 

여기에 작동원리가 상세히 나와있으니 참고하면 좋을 것 같다.

1. 양끝에서 시작

2. l과 r중 작은 기둥 찾기

2-1 둘다 같다면 l+1과 r-1을 비교한다.

2-2 작은 기둥과 두 사이 간격을 곱한 값을 합에 대입한다.

3. 합이 max 보다 크면 max 값에 합을 대입한다.

4. 기둥을 비교해 l 또는 r의 인덱스를 가운데로 당긴다.

Sourcecode

int maxArea(int* height, int heightSize)
{
    
  int l = 0;
  int r = heightSize - 1;
  int max = 0;
  int sum = 0;

  if(height[l] > height[r])  
          max = (r-l) * height[r];	
  else 
          max = (r-l) * height[l];	   

  while(l != r)
  {
      if(height[l] > height[r])  
      {
          sum = (r-l) * height[r];
          r--;	
      } 

      else if(height[l] < height[r])  
      {
          sum = (r-l) * height[l];
          l++;	
      } 
      else 
      {
          sum = (r-l) * height[l];

          if(height[l+1] > height[r-1])
              r--;
          else 
              l++;

      }

      if(sum > max) max = sum;
  }

      return max;
}

Identifying the Problem

Rotated된 array에서 target의 index를 리턴한다.

단, target이 array내에 없다면, -1을 리턴한다.

Organizing thoughts

Rotate가 가진 특성은 지난 153번 문제에서 자세히 소개했다.

오름차순과 내림차순이 가진 특성을 사용하면 쉽게 풀 수있다.

1. left랑 mid가 다른동안 반복

2.

<왼쪽 오름차순 오른쪽 오름차순인 경우>

target이 mid 보다 크다 → 오른쪽탐색

target이 mid 보다 작다 → 왼쪽탐색

<왼쪽 오름차순 오른쪽 내림차순인 경우>

Left <= target <= mid → 왼쪽탐색

그게 아니라면 → 오른쪽탐색

<왼쪽 내림차순 오른쪽 오름차순인 경우>

mid <= target <= Right → 오른쪽탐색

그게 아니라면 → 왼쪽 탐색

mid에 해당하는 값과 target이 같으면 return mid

right에 해당하는 값과 target이 같으면 return right

둘다 아니면 target이 존재하지 않는 다는 뜻이므로 -1을 리턴한다.

"그게 아니라면" 이 부분이 문제의 핵심인 듯하다.
3 4 5 6 7 1 2  에서 target이 2인 경우
2가 왼쪽 오름차순의 범위에 들어가지 않았기 때문에 오른쪽 탐색을 하도록 한다.
오름차순은 규칙성이 있지만, 내림차순은 규칙성이 없다.
따라서 오름차순범주가 아니므로, 내림차순 범위에 있다고 판단하는 것이다.

Sourcecode

int search(int* nums, int numsSize, int target)
{
	int l = 0;
	int r = numsSize-1;
	int mid = (l+r)/2;
	
	while(l!=mid)
	{
		if(nums[l] < nums[mid] && nums[mid] < nums[r]) //오름차순 오름차순
		{
			if(target > nums[mid]) l = mid;
			else if(target < nums[mid]) r = mid;
			else return mid;
		}
		else if(nums[l] < nums[mid] && nums[mid] > nums[r]) //오름차순 내림차순
		{
			if(nums[l] <= target && target <= nums[mid])	
				r = mid;
			else 
				l = mid;	
		}
		else if(nums[l] > nums[mid] && nums[mid] < nums[r]) //내림차순 오름차순
		{
			if(nums[mid] <= target && target <= nums[r])	
				l = mid;
			else 
				r = mid;	
		}
     	  	 mid = (l+r)/2;
    }
        
		if(nums[mid] == target) return mid;
		else if(nums[r] == target) return r;
		else return -1;
}