카드2_2164

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

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

출력

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

문제 풀이

문제이해

입력 : N(카드의 개수)

코드풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class card2_2164 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력 데이터 읽기
        int numberOfCards = Integer.parseInt(br.readLine());

        //큐 구현 후 카드번호만큼 개수 지정하기
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 1; i <= numberOfCards; i++) {
            queue.offer(i);
        }

        //큐안에 저장된 요소 출력하기
        while(queue.size() > 1) {
            queue.poll();//제일 위에 있는 카드 제거
            queue.offer(queue.poll()); //제일 위에 있는 카드를 제일 밑에 추가하고 출력
        }

        System.out.println(queue.poll());

    }
}

• 왜 이 문제에서 Queue라는 알고리즘을 사용했나?

카드의 가장 윗부분을 뽑아낸다고 했을 때, 가장 처음에 집어넣었던 숫자를 출력하는것과 같으므로 Last in First Out 구조인 Queue를 사용하는게 적절하다고 판단하였다.

• Queue의 구현과정을 설명하여라.

자바에서 Queue는 Queue인터페이스만 있고 별도의 클래스가 없으므로 Queue인터페이스를 구현한 클래스들을 사용해야 한다. (ArrayDeque, LinkedList, PriorityQueue)가 있다.
이 중 LinkedList는 연결 리스트 기반의 큐이다. 큐의 양쪽 끝에서 삽입과 삭제가 빠르게 가능하기 때문에 LinkedList를 이용해 구현하였다.

• 코드를 설명하여라

BufferedReader를 이용해 카드의 개수를 입력받아 저장하고 그 개수만큼 Queue에 for문을 돌려 저장한 후, Queue의 개수가 하나만 남을 때까지 poll과 offer를 반복하면 결과값을 만들어낼 수 있다.