C++로 연결 리스트의 이진수를 십진수 정수로 변환하는 방법

단일 연결 리스트(singly-linked list)의 첫 번째 노드를 가리키는 'head' 포인터가 있다고 가정해 봅시다. 연결 리스트에 있는 각 노드의 값은 0 또는 1이며, 이 연결 리스트는 어떤 숫자의 이진수 표현을 저장하고 있습니다. 우리가 해야 할 일은 연결 리스트에 담긴 이진수를 십진수 값으로 변환하여 반환하는 것입니다. 예를 들어 리스트가 [1,0,1,1,0,1]과 같다면 결과는 45가 됩니다.

문제 해결 접근 방식

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 연결 리스트의 각 노드 값을 배열(vector)로 변환합니다.

• 변환된 배열을 뒤집습니다. 이진수의 최하위 비트(LSB)부터 계산하기 위함입니다.

• 결과값 ans := 0, 자릿값 temp := 1로 초기화합니다.

• i := 0부터 x의 크기 - 1까지 반복하면서 다음을 수행합니다.

  • ans := ans + x[i] * temp

  • temp := temp * 2

• 최종적으로 ans를 반환합니다.

C++ 구현 예제

아래 구현 코드를 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class ListNode{
    public:
        int val;
        ListNode *next;
        ListNode(int data){
            val = data;
            next = NULL;
        }
};
ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return head;
}
class Solution {
public:
    vector <int> getVector(ListNode* node){
        vector <int> result;
        while(node){
            result.push_back(node->val);
            node = node->next;
        }
        return result;
    }
    int getDecimalValue(ListNode* head) {
        vector <int> x = getVector(head);
        reverse(x.begin(), x.end());
        int ans = 0;
        int temp = 1;
        for(int i = 0; i < x.size(); i++){
            ans += x[i] * temp;
            temp *= 2;
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,0,1,1,0,1};
    ListNode *head = make_list(v);
    cout << ob.getDecimalValue(head);
}

입력

[1,0,1,1,0,1]

출력

45

동작 원리 설명

[1,0,1,1,0,1]이라는 이진수를 십진수로 변환하는 과정을 살펴보겠습니다.

• 배열을 뒤집으면 [1,0,1,1,0,1]이 되고, 각 자릿값은 1, 2, 4, 8, 16, 32입니다.

• 계산: 1×1 + 0×2 + 1×4 + 1×8 + 0×16 + 1×32 = 45

참고로 이 문제는 배열 변환 없이 연결 리스트를 한 번만 순회하면서 ans = ans × 2 + 현재 노드 값 공식을 적용하면 O(n) 시간과 O(1) 공간으로 더 효율적으로 해결할 수도 있습니다.