백준 2164번 - 카드2 자바 풀이

문제 링크

문제 풀이 시간 :

문제 요약

1부터 N까지 카드가 순서대로 쌓여 있음
맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복
마지막에 남는 카드 번호를 구하는 문제

문제 풀이

이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다.

카드 더미에서 반복되는 동작은 두 가지다.

맨 앞 카드 제거
맨 앞 카드를 맨 뒤로 이동

즉, 큐로 시뮬레이션하기에 딱 맞는 문제다.

1부터 N까지 카드를 큐에 넣고 카드가 한 장 남을 때까지

맨 앞 카드 하나 버리고
다음 카드를 맨 뒤로 보내면 된다.

문제 난이도에 비해 구현도 간단해서 복잡한 규칙을 따로 찾지 않아도 충분히 해결할 수 있다.

최종 코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

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

        Deque<Integer> q = new ArrayDeque<>();
        int n = Integer.parseInt(br.readLine());

        // 1번부터 n번 카드까지 순서대로 큐에 삽입
        for (int i = 1; i <= n; i++) {
            q.addLast(i);
        }

        // 카드가 한 장 남을 때까지 반복
        while (q.size() != 1) {
            q.pollFirst();              // 맨 위 카드 버리기
            q.addLast(q.pollFirst());   // 다음 카드를 맨 아래로 이동
        }

        // 마지막으로 남은 카드 출력
        System.out.println(q.poll());
    }
}

2164번 - 카드2

문제 풀이 시간 :

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

5430번 - AC

1966번 - 프린터 큐

1158 - 요세푸스 문제

17070번 - 파이프 옮기기 1