[백준] 1158번: 요세푸스 문제 (Node.js, 링크드리스트)

[ 개발 공부 D+7 ]

문제 링크

백준 1158번 요세푸스 문제 확인하기

첫 번째 제출

연결리스트에 대한 개념을 배운 기념으로 백준에서 1158번 요세푸스 문제를 풀어보았다. 코드가 조금 길어졌던 만큼 current와 prev값을 계속 계산하면서 코드를 작성했다.

아래는 내가 제출한 첫 코드다.

function Node(data) {
  this.data = data;
  this.next = null;
}

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

function answer(n, k) {
  let result = [];
  let ll = new LinkedList();
  let current, prev;

  for (let i = 1; i < n + 1; i++) {
    current = new Node(i);

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

  current = ll.head;
  while (--k) {
    prev = current;
    current = current.next;
  }
 
  let count;
  while (--n) {
    result.push(current.data);
    prev.next = current.next;

    count = k;
    while (count--) {
      prev = current;
      current = current.next;
    }
  }
  result.push(current.data)
  return result;
}

console.log(answer(7, 3).join(", ")); //VS Code Test

당연히 틀렸다. 디버깅 해보겠다고 코드를 다시 읽어보며 current와 prev값을 계산해봤다. 머리속 풀이로는 문제를 발견하지 못하자 공책에 그림을 그려가며 current와 prev값에 집착하기 시작했다. 결국 직접 디버깅하지 못했고 백준 게시판에서 만난 착한 고수 분의 도움을 받았다.

너무 current와 prev값에 집착하는 바람에 해결책을 스스로 찾아내지 못한 부분에 대해 자괴감이 들었다.

최종 제출

const fs = require('fs');
let input = fs.readFileSync(0, 'utf-8').toString().trim().split(' ');
let n = parseInt(input[0]);
let k = parseInt(input[1]);

function Node(data) {
  this.data = data;
  this.next = null;
}

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

function answer(n, k) {
  let result = [];
  let ll = new LinkedList();
  let current, prev;

  for (let i = 1; i < n + 1; i++) {
    current = new Node(i);

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

  current = ll.head;
  let count_A = k;
  while (--count_A) {
    prev = current;
    current = current.next;
  }
  
  let count;
  while (--n) {
    result.push(current.data);
    prev.next = current.next;

    count = k;
    while (count--) {
      prev = current;
      current = current.next;
    }
  }
  result.push(current.data);
  console.log((`<${result.join(', ')}>`));
}

answer(n, k);

앞으로는 코드를 더 넓게 바라볼 수 있는 역량을 키우고 싶다!

이 1158번 문제는 추후 새로운 자바스크립트 개념을 배우게 되면 다시 풀어볼 예정이다.