[Leetcode] 1290. Convert Binary Number in a Linked List to Integer (JS)

출처

1290. Convert Binary Number in a Linked List to Integer

문제

나의 코드

이번에는 Binary Search Tree에 이어 또 다른 생소한 자료구조를 접하게 되었다. 그것은 바로 singly-linked list, 바로 연결 리스트이다. 참고자료는 유튜버 거니님의 자료구조를 쉽게 이해하게 해주는 강의!

List와 Array의 비교

연결 리스트(List)는 배열(Array)과 비교를 할 수 있습니다. 배열은 Static array 혹은 Fixed array라고 불립니다. 정적 배열이라는 뜻이겠죠? 반대로 연결 리스트는 Dynamic array, 바로 동적 배열이라는 의미입니다.

이 의미를 따지자면, Array의 사이즈를 미리 정하는 정적 배열과 달리 동적 배열인 List는 데이터가 들어올 때마다 동적으로 메모리를 할당하는 자료구조입니다.

List의 구성과 종류

먼저, 연결 리스트는 input이 올때마다 작은 저장 공간인 node를 만들어냅니다. 이 node에는 데이터를 저장할 수 있는 데이터 필드와 다음 데이터가 어디 있는지를 가리키는 포인터의 역할인 링크라는 변수가 있습니다. 이 링크라는 모양에 따라 어떤 리스트인지 아래와 같이 종류가 나뉘게 됩니다.

• 단순 연결 리스트 Singly-linked list
• 이중 연결 리스트 Doubly-linked list
• 원형 연결 리스트 Circular-linked list

추가적으로 링크는 하나당 4byte를 차지하게 됩니다.

List의 특징

1. input size를 알 수 없는 상황의 메모리 할당 효율은? List > Array
2. 데이터 하나당 추가적으로 소모되는 메모리 양은? List > Array

• 그 이유는 위에 언급했던 것처럼, 링크가 구성되어 있으며 이것이 4byte를 차지하기 때문입니다. 이중 연결 리스트라면 8byte가 되겠죠.

3. 중간 값의 추가 삭제가 용이한 자료구조는? List > Array

이러한 이유로 무조건 List가 Array보다 좋다고 판단하면 안되며, 상황에 따라 최적의 자료구조를 사용해야 한다는 점!

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {number}
 */
var getDecimalValue = function(head, result) {
  if(!result) {
    result = "";
  } result += head.val;
  
  console.log('현재값', head.val)
  console.log('결과값', result)
  
  if(!head.next){
    return parseInt(result, 2);
  }
  
  return getDecimalValue(head.next, result);
};

이러한 기본 지식을 바탕으로 구현해낸 코드! 실제로 모든 코드를 구현해낸 것은 아니고 다른 분이 parseInt 메소드를 사용하는 코드를 참고하였다. 그리고 실제로 어떠한 과정으로 로직이 진행되는지 보기 위해 콘솔창에 값을 볼 수 있도록 하였다.

현재값 1
결과값 1
현재값 0
결과값 10
현재값 1
결과값 101

이렇게 콘솔창에는 head.val가 하나씩 차곡차곡 result에 추가되는 것을 확인할 수 있었다.

다른 코드

그리고 위처럼 total 값을 0으로 지정해서 시작하고, 해당 값에 2를 곱하는 방식으로도 구현할 수 있다는 놀라운 사실! 실제로 2진법을 이러한 방법으로 계산을 할 수 있다는 게 놀라울 따름이다..

이렇게 창의적인 코드보다는 아직 나에게는 위와 같이 기본적인 이해를 먼저 쌓아가는 연습이 필요할 것 같다.

실행 결과