백준 실버4 12789번(자바)

백준 12789번 문제는 큐와 스택 자료구조를 적절히 활용해야 되는 문제이다.

처음에 문제를 이해하는데 시간을 별로 걸리지 않았지만 구현하는데 있어서 고민을 많이 한 문제였다.

쉽게 생각했으면 금방 풀 문제였지만, 너무 어렵게 문제에 접근하여 구현하는데 힘든 문제였다.

 

문제

---

 

입력 & 출력

---

 

풀이

---

 

먼저 학생 수를 N 값으로 받아주고 순서를 StringTokenizer로 받아준다.

위의 예제를 보면 현재 학생들이 있는 줄은 Queue 자료 구조를 사용하여 맨 앞에 있는 학생부터 나올 수 있게 해주고, 대기 줄은 Stack 자료 구조를 사용한다.

여기서 핵심은 start를 1로 초기화 해주는 부분이다.

 

먼저 현재 줄을 while문을 통해서 반복해주는데 현재 줄에 남아 있는 학생이 없을때 까지 진행한다.

현재 줄에 맨 앞에서 기다리고 있는 학생의 순위를 앞서 미리 정해놓은 start와 비교하여 같은지 확인한다.

만약에 같다면 해당 학생의 순위가 1인 것을 알 수 있고 해당 학생을 poll() 해준다.

위의 처리가 끝나면 start를 ++ 해줘서 다음 순위인 2를 확인하게 된다.

if문이 끝나고 else if 문을 통해서 대기 줄에 학생이 있는지 확인하고 만약 있으면 대기 줄에서 가장 앞에 있는 학생을 확인한다.

해당 학생이 start와 같다면 똑같이 pop() 을 해준다.

마지막으로 else문을 확인하면 위의 if 문과 else if문에서 조건이 맞지 않은 학생을 마지막으로 else 문에서 대기 줄에 push 해준다.

 

 

현재 줄의 while문이 끝나면 그 다음으로 대기 줄에 학생이 남아 있는지 while문을 통해서 확인한다.

앞서 확인한 while 문과 똑같은 방식으로 진행하며 start와 값이 같은지 비교해준다.

만약 대기 줄에 맨 앞에 있는 학생이 start와 다르다면 순서가 맞지 않다는 것을 알 수 있기 때문에 "Sad"를 출력해주고, 대기 줄에 학생이 없어질 때까지 정상적으로 처리되었다면 "Nice"를 출력해준다.