백준 2164번 카드2 (node.js)

나의 접근법

처음 문제를 보고 쉬운 문제구나 하고 풀이를 썼다. 그냥 배열 하나 만들어서 문제에서 제시한 대로 shift 와 push를 사용해서 구현하면 쉽게 풀릴 것 같았다 그리고 테스트를 했을때 답이 나와서 풀 수 있을것 같았다. 처음 내 코드는 다음과 같다.

//버리고 옮기고
const fs = require('fs');
const size = parseInt(fs.readFileSync('/dev/stdin').toString(),10);

const arr = new Array(size).fill().map((_, i) => parseInt(i+1))

function throwAndChange(arr) {
    while (arr.length > 1) {
        arr.shift(); // 맨 앞 요소 제거
        const toBottomItem = arr.shift(); // 제거한 다음 요소를 저장
        arr.push(toBottomItem); // 맨 뒤로 추가
    }
    return arr[0]; // 배열에 남은 요소 반환
}

const result = throwAndChange(arr);

console.log(result)

 

 

하지만 결과는 이러했다. 시간 초과가 계속 뜨길래 무엇이 문제인지 30분 정도 고민을 하다가 내가 모르는 개념이 있는 것 같아 구글링을 해봤다. 다른 사람들이 연결리스트(Linked List)를 사용 해서 푼 것을 보았고 학교에서만 배웠던 연결리스트가 여기서 쓰이는 것을 보고 조금 놀라웠고 재밌었다. 이전 코드에서 push와 shift 같은 js 메소드를 많이 쓰게 되는 구조로 코드를 작성했었는데 이것이 아마 시간 초과를 일으킨 문제가 되었던것 같다.

 

연결 리스트(Linked List)란? 

연결리스트 (Linked List) 는 배열의 요소들에 인덱스 번호를 따로 붙이지 않고, 각 노드(연결리스트에서는 데이터를 노드(Node)라고 부름)들을 포인터로 연결하는 자료구조이다.

연결 리스트에는 여러 종류가 있지만, 가장 일반적인 것은 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List)이다.

• 단일 연결 리스트: 각 요소는 데이터와 다음 요소를 가리키는 포인터로 이루어져 있습니다. 각 요소는 다음 요소만을 가리키므로 역방향으로 탐색할 수 없다.
• 이중 연결 리스트: 각 요소는 데이터와 이전 요소를 가리키는 포인터, 다음 요소를 가리키는 포인터로 이루어져 있습니다. 이로 인해 양방향으로 탐색할 수 있다.

연결 리스트는 삽입과 삭제가 빈번하게 발생하는 경우나 데이터의 크기가 변동적인 경우에 유용합니다. 또한 데이터가 메모리에 연속적으로 저장되지 않아도 되는 상황에서 사용됩니다.

 

최종 풀이

위의 연결리스트를 검색해보고 이중 연결리스트를 코드에 적용을 해보았다.

const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim()

const size = parseInt(input, 10);

class Node {
    constructor(val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    push(val) {
        const newNode = new Node(val);
        
        if(!this.head) {
            this.head = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.head;
        }
        this.tail = newNode;
        this.size++;
    }
    
    removeHead() {
        this.head = this.head.next;
        if (this.head) {
            this.head.prev = null;
        } else {
            this.tail = null;
        }
        this.size--;
    }
    
    getHead() {
        return this.head.val
    }
    
    getSize() {
        return this.size;
    }
}

const list = new LinkedList();

for(let i=1; i<=size; i++) {
    list.push(i);
}

while(true) {
    list.removeHead();
    if(list.getSize() === 1) break;
    list.push(list.getHead());
    list.removeHead();
}

console.log(list.getHead());

 

이렇게 풀이를 완료하였다. 자료구조가 이렇게 쓰일수도 있다는 것을 느낀 것 같다. 문제난이도가 올라갈수록 스택이나 이런 알고리즘이 나오는 것을 보고 더 열심히 공부해야 겠다고 생각했다.

 

기억을 하기 위해 그림을 그려서 연결 리스트를 그려봤다. 너무 허접하지만 이런식으로 그리면서 하니까 이해에 도움이 되는 것 같다.