[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의 특징
- input size를 알 수 없는 상황의 메모리 할당 효율은? List > Array
- 데이터 하나당 추가적으로 소모되는 메모리 양은? List > Array
- 그 이유는 위에 언급했던 것처럼, 링크가 구성되어 있으며 이것이
4byte
를 차지하기 때문입니다. 이중 연결 리스트라면8byte
가 되겠죠.
- 중간 값의 추가 삭제가 용이한 자료구조는? 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
에 추가되는 것을 확인할 수 있었다.
다른 코드
1 2 3 4 5 6 | var getDecimalValue = function(head, total = 0) { while (head) { total = total * 2 + head.val; head = head.next; } return total; | cs |
그리고 위처럼 total
값을 0으로 지정해서 시작하고, 해당 값에 2를 곱하는 방식으로도 구현할 수 있다는 놀라운 사실! 실제로 2진법을 이러한 방법으로 계산을 할 수 있다는 게 놀라울 따름이다..
이렇게 창의적인 코드보다는 아직 나에게는 위와 같이 기본적인 이해를 먼저 쌓아가는 연습이 필요할 것 같다.
실행 결과
Author And Source
이 문제에 관하여([Leetcode] 1290. Convert Binary Number in a Linked List to Integer (JS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hanei100/Leetcode-1290.-Convert-Binary-Number-in-a-Linked-List-to-Integer-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)