Convert Binary Number in a Linked List to Integer (Day 1)

11월에 들어 LeetCode Challenge를 매일 해보고 싶어서 블로그 글을 쓰게 됬습니다.

좀 취약하다고 생각하는 C++를 이용하여 코딩을 해보려고 합니다.

 

Reference: leetcode.com/explore/featured/card/november-leetcoding-challenge/564/week-1-november-1st-november-7th/3516/

답을 기제할 생각은 없고 이 문제 안에 쓰인 개념들을 정리해볼까 했지만

결국 제가 제출한 코드를 적었습니다. 밑에 답이 있으니 혼자 힘으로 풀고 싶은 분들은 맨 밑은 보지 마시길 바랍니다.

 

head가 있으면 val과 next를 구할 수 있는 형태의 Linked List입니다.

우선 val의 타입이 어떤지 알기 위해 쓴 메소드 입니다.

cout << typeid(head->val).name() << endl;

이렇게 프린트 하면 i가 나오더라구요.

이게 사실 정확한 방법은 아니지만 int는 i, char은 c 이렇게 나와서 대강 그렇구나 하고 넘어갔습니다.

이거에 관한 자세한 고찰은 여기에 있습니다.

 

그 다음에 생각했던건 head->val의 숫자들을 문자열로 바꾸어서 더했다가 나중에 이진수로 바꿔주는 것이었는데

그때 써본 메소드는 to_string입니다.

to_string(int)

string binstr = "";
while (condition) {
	binstr += to_string(head->val);
    head = head->next
}

그래서 룹 바깥에 binstr(binary string)이라는 변수를 만들고 룹에서 나올때까지 하나씩 문자열로 바꾸어 더해줬습니다.

그러면 저 while loop안의 조건(condition)은 어떻게 되어야 할까요?

//for conditions
1. while(head->next != NULL)
2. while(head->val != NULL)
3. while(head != NULL)

제가 시험해본것은 위의 3가지인데요, 마지막 3번째 시도가 제대로 돌아갑니다.

1번을 했을때에는 마지막 이전의 val 값을 읽고, head = head->next을 하기 때문에

마지막 tail(끝의 node를 tail이라고 읽음)을 head가 가리키고 있을때, tail의 next가 null이기 때문에

마지막 value를 건너뜁니다.

2번은 val이 0이나 1인데 숫자 0이 NULL과 같기 때문에

cout << (0==NULL? true:false) << endl;
output: 1(true)

이진수를 하나하나 읽을때에는 적합하지 않습니다.

그래서 string으로 받아서 읽었는데 생각해보니 그럴 필요가 없더라구요.

예를들어 10011같은 경우 그냥 1*2^4+0*2^3+0*2^2+1*2^1+1*2^0으로 나타낼수 있으니

바로 int로 받아서 코드를 짰습니다.

int value = 0;
multiply = 1;
while(head != NULL) {
    value += head->val*multiply;
    multiply *=2;
    head = head->next;
}

처음에는 이렇게 적었는데 이건 뒷자리부터 들어올때 제대로 돌어가더라구요.

그래서 10011은 거꾸로 1*2^4+1*2^3+1*2^0 이렇게 읽힙니다. (19여야하는데 25로 읽힘)

#include <iostream>

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int value = 0;
        int multiply = 1;
        while(head != NULL) {
            value *= multiply;
            value += head->val;
            head = head->next;
        }
    }
};

반대로 받는다고 생각하면 그냥 전에 받았던 값을 두배하고 새로운 자릿수를 더하면 되는것이었습니다.

그래서 value를 두배로 만들고 새로운 val을 더하고 (처음 돌아갈때 받은 val은 굳이 1 안 곱해도 됨) 이렇게 만들었습니다.