백준 2164번 카드2 (Python, Java)

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

2164번: 카드2

 

 

풀이 : Deque를 쓰지 않고 그냥 풀면 시간초과가 발생한다. 카드1 문제는 아무렇게나 풀어도 맞았는데 이거는 시간초과가 발생하기 때문에 Deque를 써야한다. 

 

 

1. 카드2 with Python

from collections import deque
 
cards = deque([i for i in range(int(input()), 0, -1)])
 
while len(cards) > 1:
    cards.pop()
 
    if len(cards) == 1:
        break
 
    cards.appendleft(cards.pop())
 
print(cards[0])

 

deque는 큐와 스택의 기능을 다 이용할 수 있는 자료구조이다.  파이썬 deque에 관한 것이다.

 

출처 : https://dongdongfather.tistory.com/72

출처 : https://dongdongfather.tistory.com/72

출처 : https://dongdongfather.tistory.com/72

출처 : https://dongdongfather.tistory.com/72

 

 

2. 카드2 with Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
 
public class Main_2164 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        Deque<Integer> queue = new ArrayDeque<>();
 
        int n = input.nextInt();
 
        for (int i = 0; i < n; ++i) {
            queue.addLast(i+1);
        }
 
        while (queue.size() > 1) {
            queue.pollFirst();
 
            if (queue.size() == 1) break;
 
            queue.offerLast(queue.pollFirst());
        }
 
        System.out.println(queue.pollFirst());
        
    }
}