백준BOJ/Java/Python : 2161번 카드1

2161번 : 카드1 원본

알고리즘 분류

  • 구현
  • 자료 구조

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며,
1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다.

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

N이 주어졌을 때, 버린 카드들을 순서대로 출력하고,
마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다.

풀이

  • Queue 클래스를 이용해서 풀이해야 하는 문제
  1. 먼저 들어간 자료가 먼저 나오는 FIFO(First In First Out) 방식
  2. 큐의 한 쪽은 Front로 자료가 빠져나가는 Dequeue 연산 수행
  3. 큐의 한 쪽은 Rear로 자료가 들어가는 Enqueue 연산 수행
  • Queue 클래스 객체 생성 [Java]
Queue<Integer> queue = new LinkedList<>();
  • Queue 클래스 객체 함수 [Java]
    • add, remove, element 메서드는 연산에 문제 생긴 경우 예외가 발생
    • offer, poll, peek 메서드는 연산에 문제 생긴 경우 false 또는 null 반환
// Enqueue 연산 메서드
queue.add(i + 1);
queue.offer(i + 1);

// Dequeue 연산 메서드
queue.remove();
queue.poll();

// Peek 연산 메서드 (맨 처음 저장된 객체 반환)
queue.element();
queue.peek();

소스 코드

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

public class Baek2161 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int caseNum = Integer.parseInt(br.readLine());
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < caseNum; i++) {
            queue.add(i + 1);
        }

        // queue 개수가 하나가 남을 때까지 반복
        while (queue.size() != 1) { 
            // 맨 처음에 온 숫자 출력 후 Dequeue 연산
            System.out.print(queue.poll().toString() + " ");
            // Dequeue 연산 수행 한 숫자를 queue로 Enqueue 연산
            queue.add(queue.poll());
        }

        System.out.print(queue.poll()); 
    }
}
Python
case = int(input())
queue = []
for i in range(case):
    queue.append(i)

while (len(queue) != 1):  # queue 개수가 하나가 남을 때까지 반복
    print(queue.pop(0)+1, end=' ')  # 맨 처음에 온 숫자 출력 후 Dequeue 연산
    queue.append(queue.pop(0))  # Dequeue 연산 수행 한 숫자를 queue로 Enqueue 연산

print(queue.pop()+1)
이 글이 도움이 되었나요?
0 minutes ago
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.