[2164] 카드2 card2

문제

입력

출력

예제 입력 1

6

예제 출력 1

4

My solution

function solution(i) {
    let nums = i.toString().trim().split("\n");
    let cards = Array.from({ length: nums }).map((_, i) => (i + 1).toString());
    while (cards.length > 1) {
        cards.shift();
        cards.push(cards.shift());
    }
    console.log(cards[0]);

    return cards[0];
}

test("solution", () => {
    expect(solution("6")).toBe("4");
});

큐 자료구조 예시 문제 카드2

balmostory.tistory.com/29 오늘은 큐를 이용해 백준의 카드 2문제를 풀어보도록 하겠습니다. www.acmicpc.net/problem/2164 지난 시간 보았던 것처럼 큐는 first in first로 먼저 들어간 것이 먼저 나오는 입구와 출구가 다른 자료구조입니다. def card_2(n): card=[i for i in range(1,(n+1)//2)] while n!=1: card.pop(0) l=card.pop(0) card.append(l) n-=1 return card[0] n=int(input("")) print(card_2(n)) 그 특징을 사용해 먼저 들어간 순서대로 꺼내는 방식으로 구현한 코드입니다.

https://balmostory.tistory.com/31

function solution(i) {
    let nums = i.toString().trim().split("\n");
    let cards = Array.from({ length: nums })
        .map((_, i) => i + 1)
        .filter((_, i) => !((i + 1) % 2));
    console.log(cards);

    while (cards.length > 1) {
        cards.shift();
        cards.push(cards.shift());
    }
    console.log(cards.pop());

    return;
} ...

JS 알고리즘 구현: 큐(Queue) 구현 vs Array 메서드(shift, splice) 사용했을때 속도 비교

알고리즘 코딩테스트에서 Queue 자료구조를 써야할때가 있습니다. 대표적으로 BFS를 구현할때죠. C++의 경우 STL을 통해 사용할 수 있고, Python의 경우 deque를 써서 삽입, 삭제 시 O(1)의 시간복잡도를 갖는 큐 자료구조를 활용할 수 있습니다. JavaScript의 경우 그런 라이브러리가 따로 없기 때문에, Array.shift() 또는 Array.splice(0,1) 등 array 메소드를 활용하여 큐 처럼 사용할 수 있습니다.

https://velog.io/@grap3fruit/JS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84-%ED%81%90Queue-%EA%B5%AC%ED%98%84%ED%96%88%EC%9D%84%EB%95%8C-vs-Array-%EB%A9%94%EC%84%9C%EB%93%9Cshift-splice-%EC%82%AC%EC%9A%A9%ED%96%88%EC%9D%84%EB%95%8C-%EC%86%8D%EB%8F%84-%EB%B9%84%EA%B5%90

class Queue {
    constructor(elements) {
        // * : 처음에 배열을 넣어줄 수 있다.
        this._elements = Array.isArray(elements) ? elements : [];
        // * : _offsset은 큐의 맨 앞의 값의 인덱스를 가리킨다.
        this._offset = 0;
    }

    enqueue(element) {
        this._elements.push(element);
        return this;
    }

    dequeue() {
        if (this.isEmpty()) return null;

        // 맨 앞의 값을 가지고 _offset을 한칸 이동
        const first = this.front();
        this._offset += 1;

        // 큐의 중간까지는 offset 만으로 처리가 가능하다. 성능개선, 어차피 멤버변수는 정보은닉으로 접근불가
        if (this._offset * 2 < this._elements.length) return first;

        // only remove dequeued elements when reaching half size
        // to decrease latency of shifting elements.
        this._elements = this._elements.slice(this._offset);
        this._offset = 0;
        return first;
    }

    front() {
        return this.size() > 0 ? this._elements[this._offset] : null;
    }

    back() {
        return this.size() > 0
            ? this._elements[this._elements.length - 1]
            : null;
    }

    size() {
        return this._elements.length - this._offset;
    }

    isEmpty() {
        return this.size() === 0;
    }

    clear() {
        this._elements = [];
        this._offset = 0;
    }
}

소스코드

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

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

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

        if (!this.head) {
            this.head = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
        }

        this.tail = newNode;
        this._size++;

        return newNode;
    }

    getHead() {
        return this.head.value;
    }

    removeHead() {
        this.head = this.head.next;
        this.head.prev = null;
        this._size--;
    }

    getSize() {
        return this._size;
    }
}

function solution(i) {
    let nums = i.toString().trim().split("\n");
    // console.log(cards);
    const cards = new LinkedList();
    for (let i = 1; i <= nums; i++) {
        cards.add(i);
    }
    let q = new LinkedList(cards);
    while (cards.getSize() !== 1) {
        cards.removeHead();
        cards.add(cards.getHead());
        cards.removeHead();
    }

    console.log(cards.getHead());

    return;
}

test("solution", () => {
    expect(solution("6")).toBe("4");
});