[Baekjoon (Node.js)] 2164번 카드2

📄 문제

너무 길어서 이미지로!

입출력 예제

---

😅 나의 실패 풀이

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
let targetNum = parseInt(input[0]);

function go(num) {
  let arr=[]

  for (let i = 1; i <= num; i++){
    arr.push(i)
  }

  while (arr.length != 1) {
    arr.shift()
    arr.push(arr.shift())
  }
}

go(targetNum)

바로 시간 초과 하하...

---

😂 실패 풀이 접근법 

1. arr(빈 배열)을 만들고 반복문으로 targetNum 까지 순서대로 넣어준다.

2. 반복 arr의 길이가 1일 때 까지=> 맨 앞에 요소를 없애고, 맨 뒤에 맨 앞에 요소를 없애면서 넣어준다.

3. 시간 초과... 최대한 적은 수행으로 짠 것 같은데, 이 방법 자체가 안된다는 걸 깨달았다.

---

🤔 왜 그럴까?

- 채점 중이 뜨는 걸 보면 값은 잘 나온 것 같다.

- 배열의 shift, push 로는 시간 복잡도가 커질 수 밖에 없다고 한다.

- 우리 팀 그린이 말했던 말이 떠올라 연결리스트 구조로 접근을 해야한다고 생각이 들어 책으로 공부해서 수정 시작!

 

- 구현 성공!

---

📝 나의 통과 풀이

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let targetNum = parseInt(input.shift());

function linkedListNode(data) {
  this.data = data;
  this.next = null;
  this.prev = null;
}
function linkedList() {
  this.head = null;
  this.tail = null;
  this.size = 0;
}

linkedList.prototype.insert = function (value) {
  let node = new linkedListNode(value);
  if (!this.head) {
    this.head = node;
  } else {
    this.tail.next = node;
    node.tail = this.tail;
  }
  this.tail = node;
  this.size++;
};

linkedList.prototype.remove = function () {
  this.head = this.head.next;
  this.head.tail = null;
  this.size--;
};

linkedList.prototype.checkHead = function(){
  return this.head.data;
}

linkedList.prototype.checkSize = function(){
  return this.size
}

let item = new linkedList();

for (let i = 1; i <= targetNum; i++) {
  item.insert(i);
}
while (item.checkSize() !== 1) {
  item.remove();
  item.insert(item.checkHead());
  item.remove();
}

console.log(item.checkHead());

이 맛에 문제 풀지 ㅜㅜ

---

⌨ 접근법

1. 연결리스트 구조를 prototype으로 직접 구현한다 (생성, 추가, 삭제, 헤드체크, 사이즈체크 추가)

2. 반복문으로 실패 풀이와 동일한 구조 실행

 

* 추후에 알고리즘 개념 등도 포스팅 할 예정! *

---

📚 문제 링크

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

2164번: 카드2