(백준/Java) 2164번 : 카드2 (Queue(LinkedList)와 Deque)

난이도: Silver 4

프로그래밍 언어: Java

문제명: 카드2

푼일자: 2021년 7월

 

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

 

문제풀기

처음에는 Stack 을 떠올렸으나 이는 삭제를 할 때 맨 첫번째에 있는 데이터를 삭제하지 못한다.

그래서, Queue 라는 좋은 자료구조가 있어 사용하여 풀어 보았다.

 

public class question_2164 { // 카드2
    public static void main(String[] args) throws IOException {
        var br = new BufferedReader(new InputStreamReader(System.in));
        var N = Integer.parseInt(br.readLine());

        var queue = new LinkedList<>();
        for (int i = 1; i <= N; i++)
            queue.offer(i);

        while(queue.size() > 1) {
            queue.poll();
            queue.offer(queue.poll());
        }

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

        br.close();
    }
}

사실 queue 를 쌓을 때, for 문을 사용하는 것이 마음에 들지 않았다.

그래서 찾아보니 deque(덱,데크) 라는 자료형을 Java 에서 지원한다!

 

사용해서 다시 풀어보았다.

 

public class question_2164 { // 카드2
    public static void main(String[] args) throws IOException {
        var br = new BufferedReader(new InputStreamReader(System.in));
        var N = Integer.parseInt(br.readLine());

        var deque = new ArrayDeque<>();
        while(N != 0)
            deque.offerFirst(N--);

        while(deque.size() > 1) {
            deque.removeFirst();
            deque.offerLast(deque.pollFirst());
        }

        System.out.print(deque.pollFirst());

        br.close();
    }
}

 

코드가 깔끔해졌고, 변수선언이 대폭 줄어들어서 메모리 효율이 향상되었다.

 

 

아래가 큐를 이용한 풀이이고, 위가 덱을 이용한 풀이이다.

 

속도는 소폭 늘었지만, 메모리 효율은 매우 높은 것으로 보인다.