[c/LeetCode] Add Two Numbers

1. 문제 (난이도 : medium)

2. 첫 번째 접근 아이디어

링크드 리스트를 돌면서 숫자로 가져와서 더하면 빠르게 될 것이라고 예상했음

그래서 

    while (temp != NULL)
    {
        val1 = val1 * 10 + temp->val;
        temp = temp->next;
    }

이렇게 돌면서 가져온 숫자를 거꾸로 만들어야 하니까

    while (val1)
    {
        tmp1 = tmp1 * 10 + (val1 % 10);
        val1 = val1 / 10;
    }

이렇게 변수를 하나 더 설정해서 숫자로 만드는 작업을 했음

당연히 타입은 unsigned long long으로 나름 오버플로우를 생각하긴 했음

 

그 뒤에 숫자를 더하고 

while문을 돌면서 malloc해준거에 %10으로 나머지 숫자부터 찾아서 거꾸로 넣는 작업을 했음!

처음에는 테스트 케이스들 다 맞아서 흠 당연히 맞겠지 했는데 틀렸다고 나왔음

이왜진? 의 마인드로 살펴봤는데

 

[0,8,6,5,6,8,3,5,7]

[6,7,8,0,8,5,8,9,7]

 

이 케이스와 같이 0으로 시작하는 케이스들은 당연히 숫자로 계산했을 때 자릿수가 하나 빠지기 때문에 처리를 못하는 거였음

하... 42서울에서 그렇게 NULL, 0, 오버플로우 언더플로우 등등 예외 경우 때문에 오지게 틀리는 경험을 했으면서

또 이러고 앉아있음.. 진짜 생각 좀 해라 어?

 

3. 두 번째 접근 아이디어

하여튼 그래서 다시 짜서 성공했다.

그냥 자릿수마다 계산해서 더해주고 10 이상인 수에 대해서는 1을 다음 계산할 때 더해줘야 하니, offset에 1을 저장하는 방식으로 올림 수를 계산했다. 그리고 while문의 종료조건은 l1, l2 모두가 NULL이고 올림 수도 없을 경우에 끝난다.

 

4. 결과

실행 속도는 24ms

메모리는 7.8MB 사용했다.

분명 20ms로 줄일 방법이 있을텐데 고민해봐야겠다.

 

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *p;
    struct ListNode *p_prev = NULL;
    struct ListNode *returnNode = NULL;
    struct ListNode *temp1;
    struct ListNode *temp2;
    int offset = 0;
    int result = 0;
    int turn = 0;
    int len = 0;
    
    while (true)
    {
        result = 0;
        
        temp1 = l1;
        len = 0;
        while (len < turn && temp1 != NULL)
        {
            temp1 = temp1->next;
            len++;
        }
        if (temp1 != NULL)
            result += temp1->val;
        
        temp2 = l2;
        len = 0;
        while (len < turn && temp2 != NULL)
        {
            temp2 = temp2->next;
            len++;
        }
        if (temp2 != NULL)
            result += temp2->val;
        
        if (temp1 == NULL && temp2 == NULL && offset == 0)
            break;
        result += offset;
        
        if (result >= 10)
        {
            result = result % 10;
            offset = 1;
        }
        else
            offset = 0;
        p = malloc(sizeof(struct ListNode));
        p->val = result;
        p->next = NULL;
        if (p_prev == NULL)
        {
            p_prev = p;
            returnNode = p;
        }
        else
        {
            p_prev->next = p;
            p_prev = p;
        }
        turn++;
    }
    return returnNode;
 
}