LeetCode : 2816. Double a Number Represented as a Linked List

 

문제)

노드의 값이 1,8,9인 연결 리스트가 있다.

이 연결리스트를 노드를 합친 숫자의 2배를 가진 연결리스트로 뱉어주면 됨.

189 * 2 = 378.

3=>7=>8 이런 식으로 나오면 된다.

난이도 : 중

 

소요시간 및 풀이)

분명 쉬운 문제라고 생각하고 풀었으나 정수형의 범위를 초과하는 케이스에서 통과하지 못하였다.

 

나는 노드를 순회 한 다음 값들을 벡터에 넣어서 하나의 정수로 합침.

합친 정수를 2배 해줌.

2배 해준 정수를 다시 하나씩 나눠서 벡터에 넣어줌.

벡터를 순회하면 노드를 만들어서 연결시켜줌.

 

이런 식으로 풀었다. 

 

그런데 생각해보니 굳이 정수로 합친 다음 2배를 했다가 다시 나눠줄 필요 없이, 

/= 10 연산을 통해 1을 다음 자리로 넘겨주면서 바로바로 노드를 만들어 주면 되는 거였다.

 

실패 코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* doubleIt(ListNode* head)
    {
        vector<signed long long> vec;
        auto tempNode = head;

        while (tempNode != nullptr)
        {
            auto multiVal = tempNode->val;
            tempNode = tempNode->next;
            vec.push_back(multiVal);
        }

        auto newVec = ChangeNum(vec);

        ListNode* newHead;

        //새로 만들기
        for (int i = 0; i < newVec.size(); i++)
        {
            if (i == 0)
            {
                newHead = new ListNode(newVec[i]);
                continue;
            }

            GetLastNode(newHead)->next = new ListNode(newVec[i]);
        }
            
        return newHead;
    }

    ListNode* GetLastNode(ListNode* head)
    {
        ListNode* _head = head;

        while (_head->next != nullptr)
        {
            _head = _head->next;
        }

        return _head;
    }

    vector<signed long long> ChangeNum(vector<signed long long>& vec)
    {
        vector<signed long long> newVec;
        signed long long a = 0; //int 형 범위 초과하는 케이스 있음.
        for (int i = 0; i < vec.size(); ++i)
        {
            a += vec[i] * pow(10, vec.size() - i - 1);
        }

        vec[0] = a * 2;
        signed long long num = vec[0];

        if (num == 0)
            return vec;

        while (num > 0)
        {
            newVec.push_back(num % 10);
            num /= 10;
        }

        reverse(newVec.begin(), newVec.end());

        return newVec;
    }
};

 

 

정답 코드

class Solution 
{
public:
    ListNode* doubleIt(ListNode* head) 
    {
        stack<int> values;
        int val = 0;

        while (head != nullptr) 
        {
            values.push(head->val);
            head = head->next;
        }

        ListNode* newTail = nullptr;

        while (!values.empty() || val != 0) 
        {
            newTail = new ListNode(0, newTail);

            if (!values.empty()) {
                val += values.top() * 2;
                values.pop();
            }
            newTail->val = val % 10;
            val /= 10;
        }

        return newTail;
    }
};