[백준_2164/JAVA] 카드 게임_스택, 큐 풀이

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

Queue 문제풀이

이 문제는 큐를 잘 이해하고 있는지를 묻는 문제이다.

"카드를 맨 위에서 제거하고, 그 다음 카드를 맨 아래로 옮기는 작업을 반복해 마지막 남은 카드를 찾는 것"

은 큐의 선입선출 (FIFO) 성질을 이용해 쉽게 구할 수 있다.

(...그리고 알고리즘 분류에 '큐'라고 떡하니 써있다.)

문제 풀이 순서

 

1. poll을 수행해서 front의 카드를 버린다.

2. 한번 더 poll을 수행해서 그 카드를 가장 아래의 카드 위치로 이동한다 (rear의 위치)

3. 큐의 크기가 1이 될 때 까지 과정 1~2를 반복해서 큐에 남은 원소를 출력한다.

 

Queue 코드

public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	int N=Integer.parseInt(br.readLine());
    	int result=solve(N);
    	
    	System.out.println(result);
    }
    
    // 큐로 구하는 함수
    public static int solve(int n) {
    	Queue<Integer> queue=new LinkedList<>();
    	
    	for(int i=1;i<=n;i++) {
    		queue.add(i);
    	}
    	
    	while(queue.size()>1) {
    		queue.poll();
    		int num=queue.poll();
    		queue.add(num);
    	}
    	
    	return queue.poll();
    }
}

 

 

 

---

Stack 문제풀이 (잘못된 풀이)

"카드가 차례로 1에서부터 N까지의 번호가 붙어 있으며, 1번 카드가 가장 위, N번카드가 가장 아래인 상태이다." 라는 말 에서
스택의 구조를 떠올렸다.
스택의 가장 위에 있는 카드를 pop(), 그 다음 위에 있는 카드를 pop() 하되 변수로 받은 후, 제일 밑 인덱스로(0)으로 보내는 생각을 했다.

Stack 코드

public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	int N=Integer.parseInt(br.readLine());
    	int result=solve(N);
    	
    	bw.write(String.valueOf(result));
    	

    	bw.flush();
    	bw.close();
    }
    
    public static int solve(int n) {
    	Stack<Integer> stack=new Stack<>();
    	
    	// 스택에 주어진 순서대로 정수 추가하기
    	for(int i=n;i>0;i--) {
    		stack.push(i);
    	}
    	
    	// 스택에 카드가 1장 남을때 까지 반복
    	while(stack.size()>1) {
    		stack.pop();
    		int peek=stack.pop();
    		
    		stack.add(0,peek); //스택 인덱스 0에 peek값 삽입
    	}
    	
    	return stack.pop(); //결과값
    }
       
}

하지만.. 결과는 시간초과 였다.

위 코드가 잘못된 이유

1. stack.add(0,peek)는 Vector에서 제공되는 기능으로, 스택을 큐 처럼 동작하도록 강제로 구현한 것이다..

 

2. add(0, element)는 내부적으로 배열을 이동 시켜야 하기 때문에 시간 복잡도가 O(n)이다.

- Vector의 내부 구조는 동적 배열 (Array)기반으로 동작 하기 때문에, 0번 인덱스에 요소를 삽입하려면

- 이미 존재하는 모든 요소를 한 칸 뒤로 이동 시켜야하고, 배열의 길이가 n이라면 삽입 연산에 O(n)이 소요된다.

이것은 매우 비효율적인 방법이다... N이 급격히 커지면 시간 초과가 발생한다.

 

3. 위 코드(Stack)의 시간복잡도 O(N^2), 큐로 구한 코드의 시간복잡도 O(N)

큐로 구하면 불필요한 인덱스 삽입 연산이 없기 때문에, poll()과 add()가 항상 O(1)로 처리되어 시간복잡도가 O(N) 이다.

 

 

그냥 애초에 큐로 풀라고 만들어진 문제이다. (삽입 삭제가 2개의 구간에서 발생하니까..)

 

https://velog.io/@roro/Java-Stack-Queue

[Java] - Stack & Queue

위 블로그에서 java에서 제공하는 스택과 큐의 차이에 대해 잘 설명해두었다..