[백준] 2164번 : 카드2(JAVA)

오늘도 열심히.gif

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

2164번: 카드2

위의 문제는 Baekjoon Online Judge의 단계별로 풀어보기 중 18단계

 

큐, 덱의 카테고리에 포함되어 있는 문제이다.

 

 

큐의 시간복잡도가 O(1)이어야만 풀 수 있는 문제이며

 

배열을 이용한 큐는 디큐할 때 마다 배열을 맨 앞으로 옮겨줘야 하기 때문에

 

시간 복잡도가 O(n)이라서 다른 방법으로 풀어줘야 한다.

 

 

나는 원형큐(링버퍼)를 사용하여 문제를 해결하였다.

 

문제에서는 인큐 하는 과정이 없이 단계마다 맨 위의 카드를 버리고

 

그 다음 맨 위에 있는 카드를 맨 아래로 옮기는 동작만 수행하여

 

바로 하나의 메소드 안에서 문제를 처리하였다.

 

먼저 숫자가 주어지면 큐를 생성하여 처음부터 끝까지 순서대로

 

정수를 입력하고 front에는 배열의 처음, rear에는 배열의 맨 끝을 준다.

 

그리고 문제처럼 맨위는 버리고 그 다음 맨위는 맨 밑으로 옮기는 방식으로

 

진행하다가 front 와 rear가 같아지는 순간이 1개가 남는 순간이므로

 

그 때 while문을 빠져나와 값을 리턴해주면 된다.

 

굳이 num이라는 변수를 선언하여 몇 개인지 표시하지 않아도 될 것 같다.

 

조금 알아보기 힘들게 짠 것 같기도 해서 나중에 시간날 때 한번 고쳐봐야겠다.

 

import java.util.Scanner;

class CardQueue {
	private int max;
	private int num;
	private int front;
	private int rear;
	private int[] que;
	
	public CardQueue(int size) {
		front = 0;
		max = num = size;
		que = new int[max];
		rear = max - 1;
		
		for(int i = 0; i < max; i++)
			que[i] = i + 1;
	}
	
	public int Cal() {
		if(max == 1)
			return 1;
		else {
			while(true) {
				front++;
				if(front == rear)
					break;
				if(front == max)
					front = 0;
				
				num--;
				
				rear++;
				if(rear == max)
					rear = 0;
				
				que[rear] = que[front];
				
				front++;
				if(front == max)
					front = 0;
			}
			
			return que[front];
		}
	}
	
}
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int Number = sc.nextInt();
		
		CardQueue que = new CardQueue(Number);
		
		System.out.println(que.Cal());
	}
}