CTCI | Palindrome(회문)

Cracking the Coding Interview

 

LinkedList가 Palindrome인지 검사하는 함수를 작성하라.

먼저, Palindrome이 무엇인지 알아보자. 

 

이효리의 유행어(?)중, 내이름은 이효리~ 거꾸로 해도 이효리~ 하는 노래가 있다. 물론 technically 따져보면 Palindrome은 아니지만, 앞으로 읽어도 뒤로 읽어도 똑같은 문장을 Palindrome이라고 한다. 한방향으로만 흐르는 LinkedList에서 Palindrome인지 어떻게 효율적으로 검사할 수 있을까?

 

제일 간단한 방법은, 인풋 LinkedList를 역방향으로 하나 만든 후, 그 두 Linked List가 동일한지 보는 방법이 있다. 그렇게 되면 2N의 시간이 쓰여지고, copy 버전의 Linked List를 위한 공간이 N만큼 쓰인다. 역방향으로 LinkedList를 복사하는 로직을 먼저 생각해보자.

 

 

역방향으로 존재하는 LinkedList를 복사하는 로직이다. 노드를 넣을 때, dummy node, 그러니까 가상의 head를 만들어두고, 그 head와 head의 next사이에 노드를 항상 넣는 방식이다. 이렇게 계속 한 후, 마지막에 dummy.next를 리턴하면, 역방향으로 모든 노드가 들어가서 가장 마지막 노드가 head가 된 채, 역방향 Linked List가 완성되는 것이다. 이것을 코드로 적어보자.

 

Node copyReverse(Node head){
	Node curr = head;
    Node dummy = new Node(-1);
    
    while(curr != null){
    	Node newNode = new Node(curr.val);
        newNode.next = dummy.next;
        dummy.next = newNode;
        curr = curr.next;
    }
    
    return dummy.next;
}

 

이 로직만 살펴보면 아래와 같이 정리할 수 있다.

시간 복잡도 O(n): 여기서 n은 원본 연결 리스트의 노드 개수이다. 함수는 원본 리스트의 모든 노드를 한 번씩 방문하여 새 노드를 생성하고, 더미 노드(dummy node)의 다음 노드로 추가한다. 각 노드를 처리하는 데 드는 시간은 상수이므로, 전체 시간 복잡도는 O(n)이다. 

 

공간 복잡도 O(n): 원본 리스트와 크기가 동일한 새로운 리스트를 생성하기 때문에, n개의 추가 노드가 메모리에 할당된다. 따라서 공간 복잡도는 O(n)이다.

 

이제, Reverse한 Linked List와 원본 List와 비교하는 로직을 추가해서, 문제풀이를 완성해보자.

boolean isPalindrome(Node head){
	Node curr = head;
	Node reversed = copyReverse(head);
    
    while(curr != null){
    	if(curr.val != reversed.val){
        	return false;
        }
        curr = curr.next;
        reversed = reversed.next;
    }
    
    return true;
}

 

시간 복잡도 O(n) + O(n) = O(n): 여기서 n은 리스트의 노드 개수이다. copyReverse 함수를 호출하는 데 O(n) 시간이 소요되고, 이후에 원본 리스트와 뒤집힌 리스트를 비교하는 데 또 다른 O(n) 시간이 소요된다. 이 두 단계를 합하면 전체 시간 복잡도는 O(n)이다.

 

공간 복잡도 O(n): copyReverse 함수는 원본 리스트의 뒤집힌 복사본을 생성하기 때문에, 추가적으로 O(n)의 공간을 사용한다. 여기서 n은 원본 리스트의 노드 개수이다.

 

 

이 풀이보다 더 효율적인 방법이 있을까? 재밌는 방법이 있다. 바로, 중간노드삭제 문제에서 사용했던 방법을 약간 사용하는 것인데, LinkedList의 중간이 되는 지점을 찾고, 그 과정중에 발견한 노드들을 Stack같은곳에 저장하는 것이다. 그리고 중간 노드부터 Stack에있는 노드들을 하나씩 pop하면서 비교를 하면 된다. 만약, stack에서 pop한 노드의 value와 같지 않다면, palindrome이 아닌것이다. 이 해법으로 풀게 되면, Linked List를 N번만 가면 되고, 또 Stack도 O(N)이지만, 실제로는 N/2만 사용하게 된다. 로직을 시각화 해보자.

 

 

먼저, fast와 slow 포인터를 갖고 시작하게 된다. fast 포인터가 null이라면, 이는 짝수갯수의 LinkedList인것이다. 그런 경우, 현재 노드부터 stack에서 pop을 해서 비교를 한다. 만약 하나라도 일치하지 않으면 palindrome이 아니고, 모두 일치하면, 즉, slow가 null이 될때까지 한칸씩 pop이된 값과 비교한 값들이 모두 동일했다면, palindrome으로 판정을 내린다. 만약, fast.next가 null이라면, slow는 가운데 노드를 가르키고 있을것이다. 이런 경우, slow를 slow.next로 한걸음 옮겨서 진행한다. 

 

코드를 시작하기 전, edge case는 무엇이 있을까? 먼저, head가 null인 경우, true를 리턴하기로 한다. 또한 head노드 하나일 경우 또한 palandrome으로 인정할 수 있다. 그 이외의 경우는 모두 위 로직으로 처리가 가능하다. 만약, 노드가 2개라고 해도, 한걸음을 하게 되면, 스택에는 첫번째 값이 들어가있고, fast는 null을 포인트 할것이다. 그러면 slow가 포인트한 마지막 노드와, stack에서 pop된 값만 비교한 후, 그 여부에 따라 다음 스텝으로 넘어가게 된다. 코드로 이 로직을 구현해보자.

 

boolean isPalindrome(Node head){

	if(head == null || head.next == null){
    	return true;
    }
    
	Stack<Integer> stack = new Stack<>();
    Node slow = head;
    Node fast = head;
    
    while(fast != null && fast.next != null){
    	stack.push(slow.val);
        
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if(fast != null){
    	slow = slow.next;
    }
    
    while(slow != null){
    	if(slow.val != stack.pop()){
        	return false;
        }
    }
    return true;
}

 

시간 복잡도 O(n): 여기서 n은 리스트의 노드 개수입니다. 리스트를 두 번 순회한다. 하나는 스택을 채우기 위해, 또 하나는 스택에서 값을 꺼내면서 비교하기 위해서이다. 하지만, 사실 이 순회는 N/2만큼 한 후 N/2만큼 하게 된다. 그렇기 때문에 O(N)이라고 할 수 있다.

 

공간 복잡도 O(n/2) = O(n): 스택에는 리스트의 전반부만 저장되므로, 최악의 경우 공간 복잡도는 전체 노드 수의 절반에 해당한다. 하지만 BigO 표기법에서 상수는 무시되므로, 공간 복잡도는 O(n)으로 표현할 수 있다.

 

맨 처음 구현했던 알고리즘과 같은 결과이지만, 실제로는 시간 복잡도도 N으로 2N에 비해 빠르고, 공간 복잡도도 실제로는 절반만 쓰여진다. 

 

 

 

Reference

https://www.google.com/search?sca_esv=d7ed808a3c5b3242&sca_upv=1&sxsrf=ACQVn0-YgWE9ZV3LosF7CebFDwRx8ql_RA:1712144089862&q=palindrome&uds=AMwkrPuqwXpjCzpL-buz66vNrYYDGdcZB5EYV01z2BOcNvLBcd2bLA1G9htToaM8ng0rhOmY651cSdKCIhEoOaMIS2dIjWmFzQY33WC0yBBuaVRrBFLiUT4kP31mPOHHcznTyjIt4CP1jd8JYB6mscJtKkuaW7Rp3X6ZNkfTnBx0XKO1UQfg244xltInZ1vqQ4An8pKDRRKS5UE3TAFrw-vpRgzqrdAri8sL6SHbyKcY9c3UcPbj6S5Ychyjg0aBrc5Xk2-wuU9qUv_13eoHmSqkswJepYZkYA&udm=2&prmd=ivsnmbz&sa=X&sqi=2&ved=2ahUKEwjb757i-aWFAxU1nK8BHbCwBV8QtKgLegQIDBAB&biw=1440&bih=669&dpr=2#vhid=rFNTnuiSgv6UoM&vssid=mosaic

palindrome - Google 검색

https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2002.%20Linked%20Lists/Q2_06_Palindrome/QuestionC.java

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