문제

BOJ 2164, 카드2

핵심

• 입력의 크기가 $500'000$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 1번 카드가 제일 위에 N번 카드가 제일 아래인 상태로 카드가 놓여있고, 제일 위에 있는 카드를 제일 아래로 내리는 작업을 반복하므로 이를 효율적으로 할 수 있는 큐 자료구조 사용한다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
#include <queue>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	queue<int> q;
	for (int i = 1; i <= n; ++i)
		q.push(i);
	while (q.size() > 1) {
		q.pop();
		int top = q.front();
		q.pop();
		q.push(top);
	}
	cout << q.front();
}

Java

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++)
            q.add(i);
        while (q.size() > 1) {
            q.poll();
            q.add(q.poll());
        }
        System.out.println(q.peek());
    }
}