카드2

구해야 하는 것

  • 제일 위 카드를 버리고 그 다음 제일 위의 카드를 제일 아래로 옮기는 동작을 반복했을 때 마지막에 남게 되는 카드

주어진 자료

  • 맨 위에서부터 1 ~ N 까지의 카드가 순서대로 놓여있음
  • 동작은 다음과 같음
    • 제일 위에 있는 카드를 버림
    • 남은 카드 중 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮김
    • 카드가 한 장 남을 때까지 반복

조건

  • N은 1 이상 500,000 이하

계획

  1. 큐에 1 ~ N까지 넣는다.
  2. 동작을 반복한다.
    • 큐의 크기가 1이 될 때까지 아래 과정을 반복한다.
    • 큐의 첫번째 값을 삭제한다.
    • 큐의 첫 번째 값을 꺼낸 후 삭제한다.
    • 꺼낸 값을 큐에 추가한다.
  3. 큐의 첫 번째 값을 return 한다.

실행

public class Main {
    // 동작
    public void move(Queue<Integer> q) {
        while(q.size() != 1) {
            q.remove(); // 첫 번째 값 삭제
            int first = q.poll(); // 첫 번째 값 꺼낸 후 삭제
            q.offer(first); // 꺼낸 값을 큐에 추가
        }
    }

    // 큐에 카드 넣기
    public void addCard(Queue<Integer> q, int n) {
        for(int i = 1; i <= n; i++) {
            q.add(i);
        }
    }

    public int solution(int n) {
        // 1. 큐에 1 ~ N까지 넣는다.
        Queue<Integer> q = new LinkedList<>();
        addCard(q, n);

        // 2. 동작을 반복한다.
        move(q);

        // 3. 큐의 첫 번째 값을 return 한다.
        int answer = q.peek();
        return answer;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int answer = new Main().solution(n);
        System.out.println(answer);
    }
}

반성

  • Scanner를 사용해서 입력을 받도록 했는데, BufferedReader를 사용하는게 더 빠르다고 한다. 다음부터는 BufferedReader를 써보자