[백준 알고리즘 자바] 2164 : 카드2

https://www.acmicpc.net/problem/2164

2164번: 카드2

---

문제

• N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
• 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 
• 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
• 예를 들어 N=4인 경우를 생각해 보자.  
• 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 
• 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 
• 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 
• 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
• N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

• 첫째 줄에 남게 되는 카드의 번호를 출력한다.

입출력 예제

---

풀이방식

이번 문제는 Queue 을 사용하여 푸는 문제이다.

---

설계과정

1. 큐에 N까지의 수를 담는다.

2. 맨 위의 수를 큐에서 제거한다.

3. 그 다음의 수를 큐에서 뺀 후에 다시 넣는다.

4. 큐에 1개의 수만 남아있을때 까지 반복한다.

---

풀이과정

1. 값을 입력받는 코드를 작성한다.

 

2. 메소드를 생성하고 스택을 선언한다.

 

3. 1부터 N까지 for문을 돌려서 큐에 값을 넣는다.

• 큐에는 1부터 N까지가 들어가야 하므로 0이 아닌 1부터 넣는다.

4. 큐에 들어간 원소의 개수가 0보다 크지 않을 때까지 도는 while 문을 작성한다.

• 필자는 Q.size() 로 좀 더 직절석이게 보이도록 작성하였으나 isEmpty() 를 사용해도 동일한 결과가 나온다.
• while(!Q.isEmpty)) { ... } 와 동일하다.

5. 큐에 원소가 1개가 아니라면 큐에서 값을 빼고, 그 다음에 뺀 값을 큐에 다시 넣는다.

• offer() : 순차적으로 값을 넣는다.
• poll() : 가장 먼저 보관한 값을 꺼내고 반환한다.
• 큐에 1,2,3,4가 들어갔다면 1을 뺀다. 그 다음에 2라는 값을 또 다시 뺀 후에 큐 마지막에 다시 넣는다. 이를 통해 결과적으로 큐에는 3,4,2가 들어가게 된다.

6.  위의 조건이 아니라는 것은 큐에 원소의 개수가 1개라는 의미이므로 result 변수에 큐에 값을 넣어주고 출력한다.

---

답안소스

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

public class Main {

	public int number(int N) {
		int result = 0;
		Queue<Integer> Q = new LinkedList<>();
		
		for(int i=1; i<=N; i++) {
			Q.offer(i);
		}
		
		while(Q.size() > 0) {
			if(Q.size() != 1) {
				Q.poll();
				Q.offer(Q.poll());
			} else {
				result = Q.poll();
			}
		}
		
		return result;
	}
	
	public static void main(String[] args) {
		Main card = new Main();
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		System.out.println(card.number(N));
		
	}
}