[baekjoon] 카드 2 2164 (Javascript,c++)

2164번: 카드2 (acmicpc.net)

2164번: 카드2

---

접근 방법

알고리즘 : Queue

 

1. queue를 활용한 자료구조 문제

 

// Javascript는 shift를 활용하지 않고 Linked List를 활용하여 queue 사용

---

Javascript

/**
 * 제출용. 아래 로컬용을 지우고 제출하자.
 */
//  let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
/**
 * 로컬용, 예제.txt를 생성해서 예제를 복붙하자.
 */

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

// 큐 클래스
class Queue {
  constructor() {
    this.head = null; // 제일 앞 노드
    this.rear = null; // 제일 뒤 노드
    this.length = 0; // 노드의 길이
  }

  enqueue(data) {
    // 노드 추가.
    const node = new Node(data); // data를 가진 node를 만들어준다.
    if (!this.head) {
      // 헤드가 없을 경우 head를 해당 노드로
      this.head = node;
    } else {
      this.rear.next = node; // 아닐 경우 마지막의 다음 노드로
    }
    this.rear = node; // 마지막을 해당 노드로 한다.
    this.length++;
  }

  dequeue() {
    // 노드 삭제.
    if (!this.head) {
      // 헤드가 없으면 한 개도 없는 것이므로 false를 반환.
      return false;
    }
    const data = this.head.data; // head를 head의 다음 것으로 바꿔주고 뺀 data를 return
    this.head = this.head.next;
    this.length--;

    return data;
  }
  // head를 반환하는 함수
  front() {
    // head가 있을 경우 head의 data를 반환.
    return this.head && this.head.data;
  }
  //큐의 모든 원소를 반환하는 함수
  getQueue() {
    if (!this.head) return false;
    let node = this.head;
    const array = [];
    while (node) {
      // node가 없을 때까지 array에 추가한 후 반환해준다.
      array.push(node.data);
      node = node.next;
    }
    return array;
  }
}

function solution() {
  let input = +require("fs")
    .readFileSync("input.txt") //"/dev/stdin"
    .toString()
    .trim()
    .split("\n")
    .map((val) => val.trim())[0];

  if (input === 1) {
    console.log(1);
    return;
  }

  const queue = new Queue();
  for (let i = 1; i <= input; i++) {
    queue.enqueue(i);
  }

  while (1) {
    queue.dequeue();
    let tmp = queue.front();
    if (queue.length === 1) {
      console.log(tmp);
      break;
    } else {
      queue.dequeue();
      queue.enqueue(tmp);
    }
  }
}

solution();

 

---

C++

#include <bits/stdc++.h>
using namespace std;

queue<int> q;

int main()
{
  freopen("input.txt", "r", stdin); //제출 시 삭제

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //input

    int n;
    cin>>n;

    if(n==1){
      cout<<1<<"\n";
      return 0;
    }

    for(int i=1;i<=n;i++) q.push(i);
    
    while(!q.empty()){
      q.pop();
      int tmp = q.front();
      if(q.size() == 1){
        cout<<tmp<<"\n";
        break;
      } else{
      q.pop();
      q.push(tmp);
      }
    }




    
    return 0;
  

}