원형 연결리스트 알고리즘 문제 풀이

이번 연결리스트는 원형연결리스트의 문제이다.

일반 연결리스트와 다르게 원형으로 연결되어 있다보니깐 신경써야할 게 더 많았다.

 

문제 설명

입력값 8, 2, 3

출력 값 2, 5, 8, 4, 1, 7, 3, 6 

 

- n = 8, m = 2, k = 3

- 1, 2, 3, 4, 5, 6, 7, 8 로 n의 사람이 있을 때 m = 2번부터 시작하여 k = 3번의 간격으로 이동해서 나오는 숫자들을 출력 해야한다.

 

그림으로 보면 이렇게 한 방향으로 돌면서 3칸씩 이동하며 숫자를 하나씩 추가하여 순차적으로 출력하면 된다.

 

연결리스트를 처음 봤을 때는 이해가 안되었는데 이제 어느 정도 이해도가 높아진거 같다.

우선 4가지로 나누었다.

1. n = 8 개의 node를 만들어서 원형 연결리스트를 만든다.

2. 첫 시작 head를 m = 2로 초기화해준다.

3. 원형연결리스트를 순회하면서 3칸씩 이동시키며, 결과값에 추가한다.

4. 마지막 남은 node를 추가해준다.

 

 

/* user code */
function Node(data) {
  this.data = data;
  this.next = null;
}

function LinkedList() {
  this.head = null;
}

function answer(n, m, k) {
  let result = [];
  
  // 1. Circular Linked List 만들기
  let ll = new LinkedList();
  let current, prev;

  for (let i = 1; i <= n; i++) { // n만큼 for문을 돌면서 currnet에 node를 넣어준다.
    current = new Node(i);
    if (i === 1) {
      ll.head = current;
    } else {
      prev.next = current;
    }
    prev = current;
  }
  current.next = ll.head; // 마지막 node를 첫 heal와 연결해주어 원형 연결리스트를 완성한다.

  // 2. Start node 위치 설정
  current = ll.head; // current에 첫 head로 시작
  while (--m) { // m - 1회 만큼 반복하면 시작하는 node에 맞게 이동한다.
    prev = current;
    current = current.next;
  }

  // 3. k만큼 움직이면서 제거 / 한개만 남을 때까지
  let count; // k를 증감을 하게 되면 k값이 사라지기 때문에 k값을 가지고 있을 변수를 설정
  
  while (current.next !== current) { // current값을 만날 때까지 반복
    result.push(current.data); // current값을 하나씩 result에 추가한다.
    prev.next = current.next; // 이전 node의 Next를 현재 node의 Next로 연결한다.
                              // result에 추가한 node를 제외하고 원형연결리스트를 그대로 유지한다.
    count = k;    
    while (count--) { // count값 만큼 계속해서 이동한다.
      prev = current;
      current = current.next;
    }
  }

  // 4. 혼자 남은 후보 번호를 result에 추가
  result.push(current.data);

  return result;
}

- 우선적으로 원형연결리스트를 만들어야한다.

- 그 후 while문을 통해서 prev와 current.next로 이동을 시켜주며 순회하게 하는걸 확인해야한다.

 

원형연결리스트에서 기본적인 문제같이 느껴졌다..

앞으로 더 응용을 할 수 있어야할텐데 걱정이 먼저 앞선다..