감공사

Q. Linked Lists의 마지막 Node에서 n번째 앞에 Node를 반환하는 function을 작성하라.

---Examples;
const list = new List();
list.insertLast('a');
list.insertLast('b');
list.insertLast('c');
list.insertLast('d');
fromLast(list, 2).data; // 'b'

🎈첫 번째에서부터 다음 n번째 Node와, 마지막에서부터 앞으로 n번째 Node의 간격은 같다. 생각의 전환!
을 생각하면 조금 더 쉽게 풀어나갈 수 있다.

🧨 역시나 앞서 풀었던 2문제들과 비슷하다. 하지만, 생각을 조금 다르게 해야한다.
뒤에서부터 3번 앞으로 이동하면 red Node이며, 마지막 Node는 grey이고, 간격은 3이다.
앞에서부터 3번 뒤로 이동하면 orange Node이며, 첫 번째 Node는 green이고, 간격은 3이다.

만약, slow와 fast가 시작점(green)에서 시작할 때, fast를 먼저 3번 앞으로 이동해보자.
그럼 fast는 orange를 만난다. slow는 시작점인 green을 가리키고 있다.
이제 fast가 끝(grey)에 도달할 때까지, slow와 fast를 1칸씩 이동해보자.
slow는 최종적으로 red를 가리키게 된다.

즉, 앞에서 이동하나 뒤에서 이동하나 그 간격은 같다. Node를 각각 반대로 생각하면 된다.
결과적으로, fast는 마지막 node를, slow는 뒤에서부터 n번째 떨어진 node를 의미하게 된다.

이렇게 뒤에서 앞에 n번째 값을 구할 수 있다.

🔮 while loop을 이용해 fast를 n만큼 이동시켜주고, 또 다시 while loop을 이용해 slow와 fast를 이동시켜준다.
결과적으로 slow는 뒤에서 n번째 Node를 가리키게 된다.

Full Code

Q. Linked Lists가 circular인지 확인하라(마지막 Node가 없고, 계속 순환하는 Linked List).
(맞다면 true, 아니라면 false를 반환)

--- Examples
const l = new List();
const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
l.head = a;
a.next = b;
b.next = c;
c.next = b;
circular(l) // true

🎈 토끼와 거북이가 운동장 돌기 경주를 하는데, 경주의 끝이 없다면, 언젠가는 둘이 만날(겹칠) 것이다.
라고 상상하면 조금 더 쉽게 풀어나갈 수 있다.

🧨 앞서 풀었던 Find the Midpoint 문제를 응용하면 된다.
slow와 fast의 시작점은 같고, slow는 1칸, fast는 2칸씩 이동한다.
계속 이동하다보면 slow === fast가 되는 경우가 발생할 것이고, 이걸 조건문으로 넣어 true를 return하면 된다.
만약, circular가 아니라면 while loop조건 fast.next.next를 만족하지 않으므로 while loop이 끝난 후 false를 return하면 된다.

🔮 while loop안에서 slow === fast 조건을 넣어주고, true가 반환된다면 이 Linked List는 Circular(순환)이며,
while loop의 조건인 fast.next.next를 만족시키지 못한다면 끝이 있는 Linked List이므로 Circular가 아니다.

Full Code

Q. Linked Lists의 중간 Node를 찾는 function을 구현하라.
(매개변수로 list를 받으며, Lists의 크기가 짝수라면, Lists 반의 앞 부분에서 마지막 Node를 반환하고,
counter변수나 size() method를 사용하지 않고 풀어야 한다)

🎈 토끼와 거북이의 경주를 생각해보자.
토끼가 거북이의 2배 속도로 달린다고 생각할 때, 토끼가 도착하면 거북이는 중간을 달리고 있을 것이다.

토끼 변수1, 거북이 변수1, 달리기 반복 loop을 이용해서 문제를 해결해보자.

🧨 slow와 fast변수는 같은 시작점에서 출발한다. 그리고 slow는 1칸씩, fast는 2칸씩 이동한다.
Lists 크기가 홀수일 경우를 먼저 생각해보자.
fast가 2칸씩 이동했을 경우, 항상 마지막 Node에 도착할 수 있고, 그때 slow의 위치는 중간이다.
하지만, Lists의 크기가 짝수일 경우에는 fast가 마지막 Node에 도착할 수 없다.
따라서, fast의 다음 칸은 있지만, 다음 다음 칸을 확인했을 때 Node가 없다면, 
그때 slow의 위치는 중간(즉, Lists 전체 크기에서 반을 잘랐을 때 앞부분 반의 마지막 Node)이다.

위의 내용을 아래 코드로 옮겨 보았다.

🔮 slow나 fast를 초기화할 때, list.head;를 사용해도 동일하며, while의 조건은 반드시 &&(and)로 넣어줘야 한다.

Full Code

Q. 2개의 스택(Stack)으로 큐(Queue)를 만들어라.
(어떠한 array도 만들어서는 안 되며, Stack의 push(), pop(), peek() method만 이용하여 작성해야한다)

🎈 먼저, Stack의 특징인 LIFO(Last In First Out)와 Queue의 특징인 FIFO(First In First Out)를 생각해야 한다.

큐의 add()를 구성하고 싶다면, 위의 그림처럼 그냥 1번 스택에 값을 넣어주면 된다. 이건 생각하는 것에 문제가 없다.
(편의상 앞으로 a스택, b스택이라고 이름을 정하고 얘기하겠다)
하지만, remove()와 peek()을 구성할 때 순서에 문제가 생긴다.

remove()를 구성하기 전에, peek()을 먼저 생각해보자.
a스택에서 마지막에 들어간 값을(this.data[this.data.length -1]) return 해버리면 LIFO 순서로 값이 나와버린다. 
따라서, 큐의 peek()를 구성할 때 LIFO를 FIFO로 바꿔줘야 한다.
그러기 위해서 a스택의 값을 pop()하여 b스택에 push()한다고 상상해보자. 위의 그림처럼 값이 옮겨질 것이다.
이렇게 값을 옮긴 후 b스택의 마지막 값을 가져오면 Queue의 peek()과 동일한 결과를 얻어낼 수 있다.

peek()과 구성은 같으며, 값이 제거되느냐, 아니냐의 문제다.
이렇게 값을 옮긴 후 b스택의 마지막 값을 pop()해주면 Queue의 remove()와 동일한 결과를 얻어낼 수 있다.

단, peek()과 remove()에서 모두 b스택으로 옮긴 값은 원하는 처리 후 다시 a스택으로 옮겨줘야한다.

🔮 생성자(constructor)에 2개의 스택(Stack)을 생성해준다.
(단, Stack class를 가져오거나 따로 작성해둬야 한다)

add()에서는 a스택에 값을 push()한다.

remove()에서는 a스택 값을 b스택으로 옮긴 후 제거한 후, 다시 b스택 값을 a스택으로 옮겨준다.

peek()에서는 remove()와 마찬가지로 스택간 값을 옮겨주고 마지막 값을 가져온 후, 다시 값을 옮겨주면 된다.

큐와 스택 자료구조의 특성을 이해하기 좋은 예제다.

Full Code

Q. 값을 다르게 가지고 있는 2개의 큐(Queue)를 1개의 큐(Queue)로 만드는 weave 함수(function)을 만들어라.
(단, 값을 번갈아 넣어야하며, undefined는 없어야 한다.
또한, 어떠한 array도 만들어서는 안 되며, Queue의 add, remove, peek method만 이용하여 작성해야한다)

🎈 먼저, 값이 많이 있기 때문에 반복 작업이 필요하다. 그러니 '반복문'을 먼저 떠올려야할 것이다.
그리고 undefined가 들어가면 안 되니, 값이 있는지를 확인하는 '조건문'이 있어야한다.

값이 있는지 확인하는 peek()을 반복문의 조건으로 넣을 수 있을 것이다. 값이 있다면 '반복'해야하니까.
그리고 또한 한쪽의 값이 먼저 다 소진될 수 있으니, 반복문 안에서도 값이 있는지 또 확인하는 조건문도 필요하다.

조건이 맞는다면 해당 큐에서 값을 제거한다. remove()
그리고 새로운 큐에 값을 넣어준다. add()

위처럼 간단하게 생각하고 시작하면 된다.

🔮 가장 먼저, 새로운 큐를 만들어줘야한다. const q = new Queue();
반복문의 조건은 while( srcOne.peek() || srcTwo.peek() )을 넣어 둘 중 하나의 큐에 값이 있다면 반복한다.
조건문은 if ( srcOne.peek() ) 와 if ( srcTwo.peek() )을 넣어줘서, 둘 중 하나의 큐라도 값이 있다면 실행시킨다.
if의 내부에서는 q.add( srcOne.remove() )를 통해 기존 값을 새로운 큐(q)에 넣어준다.

이렇게 반복해주면 번갈아 값을 넣는 weave algorithm이 완성된다.

Full Code