[ Linked-List ] 1290. Convert Binary Number in a Linked List to Integer - JAVA

* leetcode의 1290번 문제를 풀어보도록 하겠다.

일단 linked-list란 뭔지 알아야 풀 수 있을 것 같다.

 

 

* linked-list란?

배열인데 node라는 공간에 value와 해당 node와 연결된 이웃 node 자체 값을 갖고 있는 배열이다.

링크 리스트는 이런 식으로 한 node에 value와 다음 이웃노드의 주소값이 있는 형태로 되어 서로가 연결되어 있다.

 

 

1290의 문제를 읽어보자.

Given head which is a reference node to a singly-linked list.
The value of each node in the linked list is either 0 or 1.
The linked list holds the binary representation of a number.
Return the decimal value of the number in the linked list.
The most significant bit is at the head of the linked list.

참조형 node인 'head'라는 node가 주어지며 이 노드는 단일 linked-list이다.
이 리스트에는 각 node의 0 혹은 1로 된 value(=binary)
그리고 이웃 node 값을 갖고 있다. 이 이진법 값을 10진법 integer로 변환하여 반환하라.

Example 1:

Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10

Example 2:

Input: head = [0]
Output: 0

 

head 배열의 값이 순서대로 [1, 0, 1]인 경우 binary 값은 '101'이 되어야 한다.
따라서 비트연산자에서 <<(쉬프트)도 사용해주어야 함을 알 수 있다.

 

비트연산자 사용은 이 글을 참고할 것

[ Binary ] JAVA | 371. Sum of Two Integers (Medium)

 

 

중요한 키 포인트 2가지가 다 나왔으니 코드를 짜보자.

class Solution {
    public int getDecimalValue(ListNode head) {
        int output = head.val; // 첫 node의 value를 할당
        while(head.next != null){ // 다음 node가 존재하지 않을 때까지 while 실행
            output = output << 1;
            /*
            	101이라는 가정 하에, 현재 1이 할당되어 있으니 옆으로 한 칸 옮겨주어야
                0을 받아서 10이 되고 다시 한 칸 옮겨주어야 101이 될 수 있다.
                옮기지 않으면 그냥 1과 0의 합이 나올뿐이다.
            */
            output += head.next.val; // head.next가 null이 아니기 때문에 이웃node의 value를 더해준다.
            head = head.next; // head에 head.next를 재할당하여 while문이 돌면서 리스트를 순회하도록 한다.
        }
        return output; // integer인 ouput 반환
    }
}

 

 

더 간략하게!

class Solution {
    public int getDecimalValue(ListNode head) {
        int output = head.val;
        while(head.next != null){
            output = (output << 1) | head.next.val;
            head = head.next;
        }
        return output;
    }
}

비트 연산자 중 or( | )를 사용하여 하나라도 1일 때 1이 되는 연산을 하였다.
어차피 쉬프트 후엔 마지막 자리는 0이 되니 head.next.val이 1일 때 무조건 1이 되게끔 or로 연산하였다.
그래서 100 + 0 = 100, 100 + 1 = 101 이런 식으로 이웃노드의 value가 output에 반영될 수 있도록 한 번에 연산하였다.

비록 메모리는 0.2MB밖에 줄지 않았지만 ㅎㅎㅎ
그래도 간결한 코드 작성 연습이 되니 베리 굿~