2020.08.20 Palindrome Linked List 풀이

문제 ) linked array 가 주어졌을 때, 해당 배열이 회문 되는 지 여부를 체크하는 문제

 

알아야 할 점)

• Palindrome 회문 : 1-2-2-1, 1-2-3-4-4-3-2-1
• Math.ceil (올림), Math.floor(내림), Math.round(반올림)
• linked array list vs array (자바스크립트 배열 아님) : 삽입/삭제가 쉬움, 특별원소 찾을 때 O(n)
• Javascript Prototype (참고문헌 : 링크)

자바스크립트는 프로토타입 기반의 언어라고 한다. 어느 곳에 빈 Object 가 있고, 그 object에는 일정한 속성이 담겨 있다. 생성자를 통해서 우리는 그 object를 가져다 쓸 수 있다. 이때 객체는 언제나 함수로 생성된다. object도 사실은 함수로 생성된 객체다. 자바스크립트가 기본적으로 만들어놓은 함수이기 때문에 별도로 설정하지 않아도 사용할 수 있다.  

 

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */

 

문제로 다시 돌아와, 문제의 기본 설정에서 ListNode를 보면, ListNode의 val, next라는 속성을 가진 객체를 new라는 생성자를 통해 원하는 만큼 생성할 수 있겠다는 생각이 든다. 이 때, 참조에서 문제 함수의 인자로 주어진 head가 ListNode의 인스턴트라는 점을 간과해선 안된다. 

 

function ListNode(val, next) {
  this.val = (val===undefined ? 0 : val)
  this.next = (next===undefined ? null : next)
}

// 1 -> 2 -> 2 -> 1

let node = new ListNode(1,2)
node.next = new ListNode(node.next, 2)
node.next.next = new ListNode(node.next.next, 1)
node.next.next.next = new ListNode(node.next.next.next)

console.log(node)

/*
* ListNode {
*  val: 1,
*  next: ListNode {
*    val: 2,
*    next: ListNode { val: 2, next: ListNode { val: 4, next: null } }
*  }
* }
*/

 

풀이 ) Could you do it in O(n) time and O(1) space?

자바스크립트에서 space complexity를 고민할 필요가 없다는 stackoverflow 글을 보긴 했다. 그래서 discussion 부분에서도 javascript의 constant space 1명 밖에 답이 없었다. 현재로선 O(1) space 부분을 생략하고 문제를 풀어보았다.

 

var isPalindrome = function(head) {
  let stack = [];
  while(head) {
    stack.push(head.val)
    head = head.next; // -> 이부분 때문에 head가 false 될때까지 무한히 반복 가능하다
  }
  
  return stack.every((char, i)=>{
    return char === stack[stack.length -1 -i];
  }) // -> 이부분이 palindrome 을 체크해주는 부분이다. 
};

 

while문에서 head = head.next 이 부분으로 인해서 head가 false 가 될때까지 무한히 반복 가능하다는 점이 신기했다. runtime 측면에서 palindrome 부분을 판별하는 부분이 실행 속도를 좌우했다. 

 

---

방법 1) 문자열로 바꾸어 역순 문자열도 같은지 판별하는 법 (runtime이 3방법 중 가장 오래 걸림)

return stack.join('') === stack.reverse().join('')

 

방법2) 반으로 나눠서 같은지 비교하는 방법 : 이 방법은 n이 커질수록 유리하다.

for(let i = 0; i < stack.length / 2; i++) {
  if(stack[i] !== stack[stack.length - 1 - i]) return false
}
return true;

 

방법 3) Array.prototype.every() 매소드를 사용하는 방법 : n이 적거나 초반에 false 가 나오면 유리한 방법.

=> 위에서 보여준 방법

 

 

끝