CTCI | 리스트의 합

Cracking the Coding Interview

Linked List로 각 자릿수 하나씩 표현했다고 하고, 역순으로 배열 되어 있다면, 두 Linked List를 더해서 그 합을 Linked List로 반환해라

이 문제의 예시를 보면 다음과 같다. 두 Linked List가 있다고 하자.

 

7 -> 1 -> 6 -> null
6 -> 5 -> 9 -> 9 -> null

이 Linked Lists들은 아래 두 숫자를 나타낸다. 역순으로 저장되어있다.

 

617
9956

 

두 숫자를 더하면 어떻게 될까? 아래와 같이 계산할 수 있다.

617 + 9956 = 10573

 

이 수식 계산을 위해, 맨 앞 노드부터 더하고, 만약 둘중 한 List가 길이가 짧다면, null에 도달한 list의 노드 값은 0으로 계산해야 한다. 또한, carry 값, 즉 이전에 덧셈에서 10이상의 숫자가 되어 올림이 된 숫자가 있다면 기억해두고 그 다음 노드 계산에 써야하며, 특히, loop이 끝난 이후에도, 마지막 계산에서 carry가 있었는지 확인한 후, 만약 있었다면, 마지막에 1, carry값을 갖고있는 노드를 생성해서 붙여줘야 한다. 

 

Node sumLists(Node l1, Node l2){

	// 만약 두 노드 모두 비어있다면, 0이 1개 들어있는 노드를 리턴한다.
    // 합이 0이기 때문이며, 이는 용도에 따라 변경할 수 있다.
	if(l1 == null && l2 == null){
    	return new Node(0);
    }
	// 더한값을 저장하는 결과용 List의 dummy와 pointer 생성
    Node dummy = new Node(-1);
    Node curr = dummy;
    int carry = 0;
    while(l1 != null || l2 != null){
    
    	// Null error를 피하기 위해서, 값을 미리 찾는다.
        // 만약 현재 null에 도달했다면, 0으로 계산한다.
    	int v1 = l1 == null ? 0 : l1.val;
        int v2 = l2 == null ? 0 : l2.val;
        
        int sum = v1 + v2 + carry;
        carry = sum / 10;
        curr.next = new Node(sum % 10);
        curr = curr.next;
        
        l1 = l1 == null ? l1 : l1.next;
        l2 = l2 == null ? l2 : l2.next;
    }
    
    if(carry != 0){
    	curr.next = new Node(carry);
    }
	return dummy.next;
}

 

시간 복잡도: O(max(N,M)), 여기서 N과 M은 각각 l1과 l2 리스트의 길이이다. 이는 두 리스트 중 더 긴 리스트의 길이만큼 순회하기 때문이다. 

 

공간 복잡도: O(max(N,M)), 새로운 리스트를 생성하여 반환하기 때문에, 최악의 경우에는 입력 리스트의 길이만큼의 추가 공간이 필요하다. 여기서도 N과 M은 각각 l1과 l2 리스트의 길이를 나타낸다.

 

역방향이 아닌 정방향일때 합을 구해라

만약, 위 예시처럼이 아닌, 정방향으로 값이 저장되어있다면? 

6 -> 1 -> 7 -> null
9 -> 9 -> 5 -> 6 -> null

 

맨 끝까지 가서 7과 6을 더하고, 그 끝에서 두번째를 가고... 아주 복잡해진다. 그렇기 때문에, 이전 문제에서 난이도를 낮추기 위해, 먼저 계산이 필요한 1의자리수를 맨 첫번째 노드로 역방향으로 숫자를 linked list에 담았던 것이다. Linked List의 길이도 매번 같을 수 없기 때문에, 만약 길이가 다르면, 역시 계산을 하기 복잡해진다. 그러면 어떻게 해야할까? 이 Linked List를 역방향으로 뒤집은 다음, 위에서 했던 해법으로 다시 Sum을 하게 되면 된다.

 

그렇다면! 역방향으로 바꾸는것은 어떻게 할 수 있을까?

 

 

List를 뒤집는 핵심은, previous 노드가, 현재 노드의 next가 된다는 것이다. prev 노드를 임의로 지정하고(맨 처음에는 null 로 시작한다), 먼저, 현재 노드의 next가 나중에 바뀌기 전에, 그다음 next의 reference를 저장해둔다. 이후, curr 노드의 next를 prev로 바꾼다. 그렇게 되면 현재 노드는 next값을 뒤집어서 이전 노드를 향하게 된다. 이후, prev 포인트를 현재 노드로 옮겨서, 그 다음번 회차때 다음 노드가 현재 노드를 가르킬 수 있도록 하고, 마지막으로 curr를 next로 지정했던(reference가 바뀌기 전에 저장했던)노드를 가르키게 하면, 한 사이클이 끝난다. 이것을 curr가 null일때까지 계속 하게되면, 모든 노드는 이전 노드들을 가르키게 되고, prev포인터는 맨 마지막으로 작업을 한, 현재는 맨 첫번째인 노드를 가르키고 있게 된다. 이제 prev를 리턴하면 된다.

 

Node reverse(Node head){
	Node curr = head;
    Node prev = null;
    Node next = null;
    
    while(curr != null){
    	next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

 

이 로직으로 하면, 아래와 같이 complexity를 계산할 수 있다.

 

Time: N이 연결 리스트의 노드 개수일 때, 알고리즘은 각 노드를 정확히 한 번씩만 방문하며, 각 노드에 대해 상수 시간 연산(포인터의 변경)을 하기 때문에 시간은 노드의 개수에 비례한다. 즉 O(N)이다.

 

Space: 이 알고리즘은 추가적인 데이터 구조를 사용하지 않으며, prev, curr, next의 세 포인터만을 사용해 리스트의 노드들을 뒤집는다. 이것을 inplace 방식이라고 한다. 이러한 이유로, 사용된 추가 메모리는 입력 크기에 관계없이 일정하므로 공간 복잡도는 상수인 O(1) 이다.

 

이제 이 reverse를 통해 역방향으로 바뀐 두 LinkedList를 이전에 개발해둔 O(N)알고리즘을 이용해 Sum을 하면, 총 2N, BigO로는 O(N)으로 이 문제를 해결할 수 있다.

 

 

 

 

Reference

https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2002.%20Linked%20Lists/Q2_05_Sum_Lists

CtCI-6th-Edition/Java/Ch 02. Linked Lists/Q2_05_Sum_Lists at master · careercup/CtCI-6th-Edition