[연습문제] 15. 68 ~ 70 연결리스트

in 코딩테스트 on 연습문제




프로그래머스 문제 유형에 연결리스트가 없어서 다른 문제를 풀어본다!


68. 열차 연결

새로운 지하철 노선이 신설되어, 이를 위한 열차가 새로 반입되었다.
하지만 이 열차들은 서로 연결되어 있지 않아 현재 운행이 어려운 상태이다.
열차 운행을 위해 열차 찻간을 이어주는 프로그램을 작성하시오.
열차 별로 고유의 식별번호가 있어, 이를 기준으로 반입된 순서대로 열차 찻간을 이어주도록 한다.
입력은 배열 형태로 열차 식별번호가 주어지며, 열차 찻간을 이어주어 Linked List 형태로 반환한다.

function Train(number) {
  this.number = number;
  this.next = null;
}

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

function answer(nums) {
  let ll = new LinkedList();
  for (let i = 0; i < nums.length; i++) {
    let train = new Train(nums[i]);
    let current = ll.head;

    if (ll.head === null) ll.head = train;
    else {
      while (current.next !== null) {
        current = current.next;
      }
      current.next = train;
    }
  }
  return ll;
}

let input = [
  [4, 7, 1, 10, 6],
  [3, 10, 6, 9, 11, 3, 4],
  [5, 8, 7, 3, 4, 1, 2, 7, 10, 7],
];

LinkedList.prototype.printNode = function () {
  for (let node = this.head; node != null; node = node.next) {
    process.stdout.write(` ${node.number} -> `);
  }
  console.log("null");
};

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  answer(input[i]).printNode();
}

// #1 4 ->  7 ->  1 ->  10 ->  6 -> null
// #2 3 ->  10 ->  6 ->  9 ->  11 ->  3 ->  4 -> null
// #3 5 ->  8 ->  7 ->  3 ->  4 ->  1 ->  2 ->  7 ->  10 ->  7 -> null

자료구조 개념을 배울 때 풀었던 문제이다.
그 땐 배운 코드를 보고 했다면 이번에는 내가 직접 짜기!
복습해보니 느낀점이 연결리스트, 이중연결, 원형리스트 구현 코드 내용이 전부 이해가 가고, 생각보다 복습 시간이 적었다.
아주 기분이 좋다!


69. 서류 정리

동생에게 전달해준 서류를 순서대로 서랍에 정리해달라고 부탁했더니, 서류를 반대 순서로 넣어두었다.
다시 서류를 정렬하기 위해, 이미 정리된 순서의 반대로 서류를 역 정렬시키는 프로그램을 제작하시오.
만약 서류가 1>2>3 순으로 들어가 있다면 3>2>1로 역 정렬시켜야 한다.
입력은 동생의 가공을 통해 역 정렬된 서류가 저장되어 있는 Linked list 객체가 주어지며,
포인트 조작을 통해 파일을 변경하여 Linked List 객체를 반환한다.

function File(number) {
  this.number = number;
  this.next = null;
}

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

function answer(ll) {
  // 코드 구현 시작 영역
  let current = ll.head;
  let prev = null;
  let next;
  // 1. 역방향 정렬
  while (current != null) {
    next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  // 2. head 업데이트
  ll.head = prev;

  // 코드 구현 종료 영역
  return ll;
}

let input = [
  [7, 3, 1],
  [4, 6, 9, 1, 3],
  [3, 4, 1, 2, 7, 9, 6],
];

LinkedList.prototype.printNode = function () {
  for (let node = this.head; node != null; node = node.next) {
    process.stdout.write(`${node.number} -> `);
  }
  console.log("null");
};

LinkedList.prototype.makeFiles = function (files) {
  let current = this.head;
  let node;
  for (let i = 0; i < files.length; i++) {
    node = new File(files[i]);
    node.next = current;
    this.head = node;

    current = node;
  }
};

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);

  let ll = new LinkedList();
  ll.makeFiles(input[i]);
  answer(ll).printNode();
}

// #1 7 -> 3 -> 1 -> null
// #2 4 -> 6 -> 9 -> 1 -> 3 -> null
// #3 3 -> 4 -> 1 -> 2 -> 7 -> 9 -> 6 -> null

예전에는 이해가 안갔던 부분이었는데, 이제는 이해가 됐다!
연결리스트에서 역방향으로 뒤집는 방법 기억해두기.
prev, current, next 세개의 변수가 필요하다.
뒤집는 건 이중연결리스트면 진짜 쉬울텐데…..!!!!



70. 대표 선출

마을에 대표를 선출해야 한다.
모두 자신이 대표가 되고 싶어 하며, 아래 규칙을 통해 대표를 선출하기로 하였다.
규칙은 먼저 원탁에 둘러 앉아 시계 방향으로 1번부터 n번까지 번호를 부여한다.
그리고 주사위를 통해 굴러나온 숫자 m의 사람을 제외하고, 그 다음으로 나온 주사위 숫자 k만큼 이동해가며 대표 후보에서 제외시킨다.
이렇게 순회하여 1명이 남을 때까지 반복해 마을의 대표를 선출하기로 하였다.
n, m, k가 주어졌을 때 대표 후보에서 제외되는 번호를 출력해주는 프로그램을 제작하시오.
입력은 n, m, k의 자연수가 주어지며, 대표 후보에서 제외되는 번호를 순차적으로 배열로 반환한다.

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++) {
    current = new Node(i);

    if (i === 1) ll.head = current;
    else prev.next = current;

    prev = current;
  }
  current.next = ll.head;

  // 2. Start node 위치 설정
  current = ll.head;
  while (--m) {
    prev = current;
    current = current.next;
  }

  // 3. 후보자들 중 k만큼 움직이면서 제거 => 단, 혼자 남을 때
  let cnt;
  while (current.next != current) {
    // 노드가 자기자신 1개밖에 없다는 의미
    result.push(current.data);
    prev.next = current.next;

    cnt = k;
    while (cnt--) {
      prev = current;
      current = current.next;
    }
  }

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

  // 코드 구현 종료 영역
  return result;
}

let input = [
  [8, 2, 3],
  [10, 2, 3],
  [10, 5, 7],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  console.log(answer(input[i][0], input[i][1], input[i][2]));
}

// #1[
//   2, 5, 8, 4,
//   1, 7, 3, 6
// ]
// #2[
//    2, 5, 8, 1, 6,
//   10, 7, 4, 9, 3
// ]
// #3[
//   5, 2, 10, 9, 1,
//   4, 8,  3, 6, 7
// ]

아직까지도 알듯 말듯 하면서 내가 직접 구현하기는 조금 버겁다.
append 작업을 할 때, 위 코드 1번을 참고해서 간단하게 구하자. (추가할때마다 끝까지 순회 안해도 된다.)
연결리스트에서 삭제는 포인터 연결을 통해 이루어진다는 점 기억하기.
반복 횟수 조절은 while 문 사용하기.

더이상 연결리스트 문제에 쫄지 않기!! 이론은 완벽(?)하다. 응용만 잘하자!