[BOJ] 2164번 : 카드2 (자료구조)

백준 2164번 : 카드2

🔗 문제 링크

https://www.acmicpc.net/problem/2164

2164번: 카드2

 

---

💬 문제

 큐(queue) 에 대한 이해가 있다면 더 잘 이해할 수 있고, 큐를 몰라도 쉽게 이해할 수 있는 문제이다.

 

1. 숫자 N이 주어지므로 1부터 N까지 담고 있는 배열을 생성해준다.
2. 맨 위에 있는 수, 즉 배열 첫 번째 요소를 제거(shift)해준다.
3. 그 다음 위에 있는 수를 빼서(shift) 맨 밑으로 옮겨준다(push).
4. 그리고 단 1장의 숫자가 남을 때까지 반복한다.

 

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 N만 주어진다.

입력값으로 N을 받아와 N개의 수가 들어있는 배열을 생성하기만 하면 된다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

🔑 풀이

위의 방식대로 아래처럼 풀었다.

 

• 숫자 1부터 N까지 들어있는 배열을 생성하기 위해  Array.from 을 사용하였다.
  Array.from에 대해선 References를 참고바람
  
  
• 1부터 넣어야 하므로 (v, i) => i가 아니라, i +1로 하였다.
  i부터 하면 0부터 배열에 삽입된다
  
  
• 맨 위의 숫자 카드를 제거하고(shift), 그 다음으로 위에 있는 수를 빼서(shift) 맨 밑에 삽입(push)해주었다.
  
  
• 이 작업을 숫자 카드가 1개가 남을 때까지 돌려주고, 1개가 남았을 때 그 카드 숫자를 출력해주었다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim();
const arr = Array.from({ length: parseInt(input)}, (v, i) => i + 1);

solution(arr);

function solution(arr) {
  while(arr.length > 1) {
    // 1. 맨 위에 있는 1부터 제거
    arr.shift();
    // 2. 제일 위에 있는 수를 맨밑으로 이동
    arr.push(arr.shift());
  }
  console.log(arr[0]);
}

 

하지만...시간초과...

백준의 인심은 너무 각박하다ㅠㅠ

 

 

---

🎯 풀이를 위한 개념 설명

원인진단

위와 같은 풀이에서 while문을 돌며 배열의 요소를 삭제하고 삽입했다. 하지만 삽입과 삭제는 기존 요소들에 새로운 index 번호를 매기고 이 과정이 늘어날수록 시간 복잡도는 커질 수밖에 없다.

 

 연결리스트 (Linked List) 

 

따라서 시간초과 문제 해결을 위해 구글링을 하였고, 이를 위해 "연결리스트"라는 자료구조를 사용해보고자 한다.

 연결리스트(Linked List) 는 index 번호를 사용하는 배열과 달리 연결(link)을 이용해 구현한 리스트를 말한다.

하나의 요소 안에 데이터 뿐만 아니라, 다음 요소의 주소를 담고 있어 index가 없어도 각각의 값들을 확인할 수 있다.

더 자세한 내용은 아래의 게시글에 정리해두었다.

 

https://valueengine.tistory.com/6

[자료구조] 연결리스트 (Linked List)

 

---

🔑 연결리스트를 사용한 풀이1

위 게시글에 정리한 것처럼 연결리스트에 대해 학습하고 그에 맞춰 코드를 짜봤다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim();
const num = parseInt(input);

// 노드 클래스
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// LinkedList 클래스 설정
class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  add(value) {
    const node = new Node(value);
    let current;

    if (this.head) {  // 기존 노드가 있을 때
      current = this.head;

      while (current.next) {
        current = current.next;
      }
      current.next = node;

    } else {  // 기존 노드가 없을때
      this.head = node;
    }
    this.length++;
    return node;
  }

  remove() {  // 맨 앞 노드 제거
    let remove = this.head;
    this.head = this.head.next;
    this.length--;
    return remove;
  }

  getHead() {  // HEAD의 값 가져오기
    return this.head.value;
  }
}

function solution(num) {
  const cards = new LinkedList();
  for (let i = 1; i <= num; i++) {
    cards.add(i);
  }

  while(cards.length > 1) {
    // 1. 맨 위에 있는 수 제거
    cards.remove();
    // 2. 그다음 위에 있는 수를 맨밑으로 이동
    cards.add(cards.getHead());
    cards.remove();
  }
  return cards.getHead();
}

const card = solution(num);
console.log(card);

 

하지만... 이 역시도 시간초과...

백준 너무 각박한 것 같다....

 

 

---

🔑 연결리스트를 사용한 풀이2

그래서 단일 연결리스트가 아니라 HEAD와 TAIL 2가지 주소를 동시에 가지고 있는 이중(양방향) 연결리스트로 풀어보았다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim();
const num = parseInt(input);

// 노드 클래스
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  add(value) {
    const node = new Node(value);

    if (this.head) {  // 기존 노드가 있을 때
      this.tail.next = node;
      node.prev = this.tail;

    } else {  // 기존 노드가 없을때
      this.head = node;
    }
    this.tail = node;
    this.length++;
    return node;
  }

  remove() {  // 맨 앞 노드 제거
    this.head = this.head.next;
    this.head.prev = null;
    this.length--;
  }

  getHead() {  // HEAD의 값 가져오기
    return this.head.value;
  }
}

function solution(num) {
  const cards = new LinkedList();
  for (let i = 1; i <= num; i++) {
    cards.add(i);
  }

  while(cards.length > 1) {
    // 1. 맨 위에 있는 수 제거
    cards.remove();
    // 2. 그다음 위에 있는 수를 맨밑으로 이동
    cards.add(cards.getHead());
    cards.remove();
  }
  return cards.getHead();
}

const card = solution(num);
console.log(card);

 

이렇게 푸니 다행히 통과..

 

문제 자체를 이해하는 데는 어렵지 않지만, 시간 복잡도 때문에 문제를 푸는 데 고생을 했다.

그렇지만 그 과정을 통해 새로운 자료구조인 "연결리스트(Linked List)"에 대해 확실히 학습할 수 있었다.

 

---

References (Array.from)

 

• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from