[백준] 1835_카드 / 덱 deque

 

 

Sliver

 

 

문제

 

1부터 N까지의 숫자가 적힌 카드가 있다. 찬유는 이 카드를 가지고 마술을 하려 한다.

마술을 하는 순서는 다음과 같다.

1. 먼저 1부터 N까지의 숫자가 적힌 카드에서 첫 번째 카드를 가장 뒤로 옮긴다. 그러고 나서 첫 번째 카드를 책상 위에 올려놓는다. 그런데 그 카드는 1이 되어야 한다.
2. 그리고 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고, 또 가장 앞에 있는 카드를 가장 뒤로 옮긴다.(2번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는다. 그런데 그 카드는 2가 되어야 한다.
3. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고... (3번 반복) 그리고 가장 앞에 있는 카드를 책상위에 올려놓는데 그것은 3이 된다.
4. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고.. (4번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는데 그것은 4이다.
5. 위 과정을 계속 반복하여 N번 카드만 남을 때 까지 반복한다.

위와 같은 카드를 하려면 미리 카드의 순서를 알고 있어야 한다.

카드의 개수 N이 주어져 있을 때 위의 마술을 하기 위한 카드의 초기 순서를 구하는 프로그램을 작성하시오.

 

 

입력

 

첫 번째 줄에 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

 

 

출력

 

첫 번째 줄부터 N번째 줄까지 차례로 카드의 순서를 출력한다.

 

 

---

 

풀이

 

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Deque<Integer> dq = new LinkedList<>();
        
        dq.offerFirst(N); // 초기값 삽입
        for(int i=N-1; i>=1; i--){
            dq.offerFirst(i);
            int rotate = i%dq.size(); // 필요한 회전 횟수 계산
            for(int j=0; j<rotate; j++){
                dq.offerFirst(dq.pollLast());
            }
        }

        StringBuilder sb = new StringBuilder();
        while(!dq.isEmpty()){
            sb.append(dq.pollFirst()).append(" ");
        }
        
        System.out.println(sb);
        sc.close();
    }
}

 

 

해결방법

 

자료구조 덱을 사용하여 마술을 반대로 수행해 숫자의 원래 위치를 구한다. 

1. 초기 덱에 가장 마지막이 될 숫자를 삽입한다. 
2. i를 N-1 부터 1까지 아래작업을 반복한다. 
   • i를 덱의 맨 앞에 삽입한다
   • i%dq.size() 연산으로 회전 횟수를 계산한다
   • 계산된 횟수만큼 덱을 뒤에서 앞으로 회전시킨다

 

사용한 자료구조

• 덱(Deque): 양방향 삽입 및 삭제가 가능한 자료구조이며, 데이터를 회선 시키는 작업을 효율적으로 수행할 수 있다. 

 

 

 

 

---

 

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