[アルゴリズム]白駿2164号-カード2
質問リンク:https://www.acmicpc.net/problem/2164
カードがN枚あります.各カードには順番に1からNの番号が貼られており、1番札が一番上に、N番札が一番下に、順番にカードが置かれています.
カードが1枚残るまで、以下の動作を繰り返します.まず、一番上の札を地面に投げます.そして、一番上のカードを一番下のカードの下に移動します.
例えば、N=4とする.カードは一番上から1234の順番に並べられています.1を投げてまだ234残っています.ここで2を一番下に移動すると342です.3を42に、4を下に移動すると24になります.最後に2を捨てて、残りのカードは4になりました.
Nが付与されると、最後に残ったカードを取得するプログラムを作成してください.
第1行は整数N(1≦N≦500000)を与える.
最初の行に残っているカード番号を出力します.
最初は
一番上のカードを一番下に送る演算は
質問する
カードがN枚あります.各カードには順番に1からNの番号が貼られており、1番札が一番上に、N番札が一番下に、順番にカードが置かれています.
カードが1枚残るまで、以下の動作を繰り返します.まず、一番上の札を地面に投げます.そして、一番上のカードを一番下のカードの下に移動します.
例えば、N=4とする.カードは一番上から1234の順番に並べられています.1を投げてまだ234残っています.ここで2を一番下に移動すると342です.3を42に、4を下に移動すると24になります.最後に2を捨てて、残りのカードは4になりました.
Nが付与されると、最後に残ったカードを取得するプログラムを作成してください.
入力
第1行は整数N(1≦N≦500000)を与える.
しゅつりょく
最初の行に残っているカード番号を出力します.
のり付け
最初は
ArrayList
を使って問題を解き、出力は正しいが、提出時に何をしてもタイムアウトする.質問文では、ArrayList
はshift演算において時間複雑度がO(n)
であることを示すため、O(1)
の時間複雑度を有するQueue
を用いて問題を解く.一番上のカードを一番下に送る演算は
list.add(list.remove())
行に実現される.コード#コード#
//https://velog.io/@cjhlsb
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
int num = sc.nextInt();
Queue <Integer> list = new LinkedList<Integer>();
for(int i=1;i<=num;i++)
{
list.add(i);
}
while(list.size() != 1) {
list.remove();
list.add(list.remove());
}
System.out.println(list.poll());
}
}
Reference
この問題について([アルゴリズム]白駿2164号-カード2), 我々は、より多くの情報をここで見つけました https://velog.io/@cjhlsb/Algorithm-백준-2164번-카드2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol