[BaekJoon] #2164 - 카드2 [Java][C++]

문제 링크

---

1. 아이디어

BaekJoon 2161번 - 카드1 문제에서 $N$의 범위가 더 커지고 마지막에 남게 되는 카드만 출력하는 문제로 여전히 큐를 활용하면 해결할 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = 입력값 n)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            q.offer(i);
        }

        while (q.size() > 1) {
            q.poll();
            q.offer(q.poll());
        }

        System.out.println(q.peek());
    }
}

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }

    while (q.size() > 1) {
        q.pop();
        q.push(q.front());
        q.pop();
    }
    cout << q.front();
}

---