[백준 2164] 카드2

문제

 

2164번: 카드2

 

문제풀이

 문제에 나와있는대로 따라가면 된다. 1)제일위에 카드를 버린다. 2) 그 다음 제일 위의 카드를 꺼낸다. 3) 꺼낸 카드를 맨 뒤로 보낸다. 이걸 카드가 하나남을때 까지 반복한다. 

 

주의 해야할 점은 ArrayList로 구현하게되면 시간초과가 난다. 입력이 500,000이기 때문인 것 같은데, LinkedList로 구현하면 된다. 

 

 

보완점

 

 입력값에 따라 ArrayList를 쓸지 LinkedList를 쓸지를 판단해야한다. 여기서 메인 연산은 삭제이다. ArrayList는 내부에 배열로 구현되어있다. 따라서 맨 앞에 있는 elements를 삭제하면 shift연산을 하는데 시간이 오래걸린다. 따라서 삭제에 시간이 안드는 LinkedList로 구현해야한다. 

 

ArrayList

package queue;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Card2 {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int N=in.nextInt();
		
		Queue<Integer> cardList=new LinkedList<Integer>();
		//ArrayList<Integer> cardList=new ArrayList<Integer>();
		for(int i=1;i<=N;i++) {
			cardList.add(i);
		}
		
		while(cardList.size()!=1) {
			cardList.remove();
			int card=cardList.remove();
			cardList.add(card);
		}
		
		System.out.println(cardList.poll());
	}
}

 

 

 

LinkedList

package queue;

import java.util.ArrayList;
import java.util.Scanner;

public class Card2 {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int N=in.nextInt();
		
		ArrayList<Integer> cardList=new ArrayList<Integer>();
		for(int i=1;i<=N;i++) {
			cardList.add(i);
		}
		
		while(cardList.size()!=1) {
			cardList.remove(0);
			int card=cardList.remove(0);
			cardList.add(card);
		}
		
		System.out.println(cardList.get(0));
	}
}