백준 12789: 도키도키 간식드리미(java)

문제

---

풀이

스택과 큐를 이용하여 풀었다.

메인 대기열(현재 대기열)을 큐로, 한 명 씩 설 수 있는 공간(옆 대기열)을 스택으로 만들었다.

메인 대기열을 스캔하며 현재 순번이 아닌 사람은 옆 대기열로 보낸다.

while(!queue.isEmpty()) {	//현재 대기열 빌 때까지
	if(queue.peek()==turn) {
		queue.poll();
		turn++;
	}
	else if(!stack.isEmpty()&&stack.peek()==turn) {
		stack.pop();
		turn++;
	}
	else
		stack.push(queue.poll());
}

큐의 front값이 turn과 일치하면(turn=1로 초기화하였다) 간식을 받은 것으로 간주하여 해당 값을 삭제하고 turn을 1 증가시킨다(다음 사람으로 넘어가야 하므로). 메인 대기열에서 turn 번호를 가진 사람이 없을 경우 옆 대기열을 스캔하고(else if문), 옆 대기열 스택에서 순번인 사람이 나왔을 경우 마찬가지로 해당 값을 삭제하고 turn을 1 증가시킨다. 메인 대기열과 옆 대기열 모두에 차례인 사람이 없을 경우(else문) 메인 대기열 front의 사람을 옆 대기열로 이동한다.

while(!stack.isEmpty()) {		//옆 대기열만 남았을 때
	if(stack.peek()==turn) {
		stack.pop();
		turn++;
	}
	else {
		System.out.println("Sad");
		return;
}

메인 대기열 스캔이 종료되어 옆 대기열에만 사람이 남았을 때도 유사하게 반복한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Stack;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> stack=new Stack<>();
		Queue<Integer> queue=new LinkedList<>();
		StringTokenizer st;
		
		int N=Integer.parseInt(in.readLine());
		st=new StringTokenizer(in.readLine());
		for(int i=0; i<N; i++) {
			queue.add(Integer.parseInt(st.nextToken()));
		}
		
		int turn=1;	//입장 순서
        
		while(!queue.isEmpty()) {	//현재 대기열 빌 때까지
			if(queue.peek()==turn) {
				queue.poll();
				turn++;
			}
			else if(!stack.isEmpty()&&stack.peek()==turn) {
				stack.pop();
				turn++;
			}
			else
				stack.push(queue.poll());
		}
		while(!stack.isEmpty()) {		//옆 대기열만 남았을 때
			if(stack.peek()==turn) {
				stack.pop();
				turn++;
			}
			else {
				System.out.println("Sad");
				return;
			}
		}//end of while
		System.out.println("Nice");
	}
}