[JAVA] 2164. 카드 2

규칙을 찾아보면 1부터 N까지일 경우 순서대로 홀수는 계속해서 버려지고 짝수는 뒤로 간다.

이 규칙을 찾아 for문을 돌렸고, 큐를 만들어 짝수는 큐에 넣어주었다.

 

그 후 while문을 통해 버림과 뒤에 겹침의 연산을 처리했고, while문의 연산은 짝수를 기준으로 하였으므로, 

홀수에서는 무조건 while문을 들어가기 전에 한번 뒤로 붙임 처리를 해주어야 한다.

while문 안에서도 연산 중 1개의 카드만 남게될 시 while문을 종료하고 그 카드를 출력해주어야 한다.

 

또한, N이 1일 경우는 위의 연산이 필요하지 않고, 무조건 1개의 카드가 존재하므로 바로 1을 리턴해주었다.

 

 

package algo;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class B_2164_카드2 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        Queue<Integer> q = new LinkedList<>();
        // ** 만약 1이라면 바로 1을 출력 후 연산 끝.
        if (N == 1) {
            System.out.println(1);
            return;
        }
        // 우선 N까지 홀수는 버리고 짝수는 아래로 넣기위해 Queue에 넣는다.
        for (int i = 1; i <= N; i++) {
            if (i % 2 == 0) {
                q.offer(i);
            }
        }
        // ** N이 홀수이면 while의 반복을 가기 전 뒤로 넘겨주어야 함.
        // while은 짝수를 기준으로 버리기부터 진행하기 때문
        if (N % 2 != 0) {
            q.offer(q.poll());
        }
        // 마지막 하나의 카드가 남길 때까지
        while (q.size() > 1) {
            q.poll();
            if (q.size() == 1) // * 카드가 마지막 카드라면 break;
                break;
            else // 그렇지 않다면 다시 뒤로
                q.offer(q.poll());
        }
        System.out.println(q.poll());
    }
}