Add Two Number

문제: https://leetcode.com/problems/add-two-numbers/

오랜만에 알고리즘 문제풀이를 포스팅한다.
코드스쿼드 cs과정을 진행하면서 첫주차에 배웠던 반가산기 전가산기가 생각이나서 쉽게 풀 수 있었다. 그때 앞에서부터 계산해서 편하다라고만 생각했는데 알고리즘 문제로 비슷한게 나오니 재미있었다.
블로그에 작성할만큼의 난이도 있는 문제는 아니고 반가산기? 이런걸 배워야만 풀 수있는 문제는 전혀 아니지만 cs과정이 기억이 난게 신기해서 포스팅으로 남기려고한다.

혹시나 이 글을 구경하시는 코드스쿼드 분들은 문제 한번씩 풀어보는 것을 추천드릴게요~!

해결과정

문제를 보면 특징이 있다. 앞에서 부터 더해간다. 즉 앞에서 부터 더하고 10이 넘는다면 올림(carry)을 따로 처리해줘서 해결해주면 된다.

1. l1,l2가 있을 때까지 while문으로 순회한다.
   sum = l1.val + l2.val + carry sum에 저 3값을 더해주어서 10과 비교해서 carry를 결정해준다.

2. l1,l2를 모두 담고 마지막에 carry가 남아있다면 carry도 마지막에 추가해준다.

code

const addTwoNumbers = (l1, l2) => {
  let carry = 0;
  const head = new ListNode();
  let currentNode = head;
  while (l1 || l2) {
    let sum = carry;
    if (l1) {
      sum += l1.val;
      l1 = l1.next;
    }
    if (l2) {
      sum += l2.val;
      l2 = l2.next;
    }

    if (sum >= 10) {
      carry = 1;
      sum -= 10;
    } else carry = 0;

    currentNode.next = new ListNode(sum);
    currentNode = currentNode.next;
  }

  if (carry) {
    currentNode.next = new ListNode(carry);
  }
  return head.next;
};

Swap Nodes in Pairs

문제: https://leetcode.com/problems/swap-nodes-in-pairs/

이 문제도 쉬운 문제다. 하지만 재귀로 푸는 방식을 보는데 이게 도대체 무슨 말일까.. 라는 생각을 하게 되어서 나름 정리를 해보고자 포스팅을 한다.

해결방법1

내가 푼 쉬운 방법이다.
1. node.next를 먼저 붙여준다.
2. node를 붙여준다.
3. 홀수일 경우 node가 하나 남아있기 때문에 남아있다면 뒤에 붙여준다.

code

const swapPairs = (node) => {
  const head = new ListNode();
  let currentNode = head;
  while (node && node.next) {
    currentNode.next = new ListNode(node.next.val);
    currentNode = currentNode.next;
    currentNode.next = new ListNode(node.val);
    currentNode = currentNode.next;
    node = node.next.next;
  }
  if (node) currentNode.next = new ListNode(node.val);
  return head.next;
};

해결방법 - 재귀

문제의 재귀 풀이방법이다. 한번 예시로 작성해보니 이해가된다.
아래 코드를 순서대로 풀어서 재귀를 구현해보면서 이해하자.
ex)

1. swapPairs(1-2-3-4-5)
temp = node.next | temp=> 2-3-4-5
node.next = temp.next | node => 1-3-4-5
temp.next = node | temp => 2-1-3-4-5
node.next = swapPairs(node.next) | node => 1-swapPairs(3-4-5)
   즉, node뒤에 새로 swap한 nodelist가 붙는다. 이 node는 temp.next에 붙어있기 때문에 마지막에는 최종 정렬된 temp가 반환되는 것이다. 예시를 끝까지 한번 해보자.
2. swapPairs(3-4-5)
temp = node.next | temp=> 4-5
node.next = temp.next | node => 3-5
temp.next = node | temp => 4-3-5
node.next = swapPairs(node.next) | node => 3-swapPairs(5)
3. swapPairs(5)
   5반환
   2.swapPairs(3-4-5)의 temp => 4-3-5
4. swapPairs(3-4-5)
   4-3-5반환
   1.swapPairs(1-2-3-4-5)의 temp => 2-1-4-3-5
5. temp => 2-1-4-3-5 반환

아래의 코드가 위의 예시처럼 구현된다. 아래 그림의 순서대로 흘러간다.

code

const swapPairs = (node) => {
  if (node === null || node.next === null) return node;
  let temp = node.next;
  node.next = temp.next;
  temp.next = node;
  node.next = swapPairs(node.next);
  return temp;
};

마무리

재귀가 길지도 않은데 왜 이렇게 이해가 안될까 싶다. 집중력이 떨어져서 안된다고 믿고싶다..ㅋ😂 특히 링크드리스트를 재귀로 구현하는걸 더 어려워 하는 것 같다.
다행히 leetcode는 사람들이 풀이를 올릴 수 있고 그 풀이를 확인 할 수 있어서 그 코드를 보면서 많이 배울 수 있어서 좋다.