백준 12789번 - 도키도키 간식드리미

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

 

 

 

• 접근 방식

문제에서 현재 줄 서있는 곳에서 처음부터 하나씩 비교해서 찾는 수가 아닐경우 밑의 공간으로 집어넣고, 마지막에 밑의 줄을 한번에 비교해서 문제를 풀기로 마음 먹었다. 여기서 현재 줄은 FIFO 이니까 queue로, 밑의 줄 공간은 LIFO 이니까 스택으로 잡자고 생각했다.

 

 

 

 

• 논리 흐름(알고리즘)

현재 줄을 queue로 생성하여 입력값을 받은 후, 간식받을 선을 지날 번호를 지정해 준다. 즉 지정 번호가 나타날 경우에만 다음 단계로 넘어간다. 

우선 현재의 줄에서 간식 받을 번호(지정 번호)와 첫 순서 번호를 비교해 가며 찾는 수일 경우 그대로 pop해준 후 지정 번호를 다음 번호로 넘긴 후 과정을 반복 한다. 

만약 지정 번호보다 현재 줄의 첫 번호가 크다면(작은 경우엔 이미 pop되기 때문에) 밑의 줄서는 공간으로 번호를 넘겨준다. 

여기서 주의할 점은 번호를 밑으로 넘겨주기 전에, 밑에 공간의 첫번째 순서와도 비교해 주고 지정값과 같으면 밑의 공간의 수를 pop해 준 후 다음 지정값으로 넘어가 순서를 반복해준다.

이 과정을 현재 줄의 사람이 없어질때 가지 반복 후에 밑의 줄의 사람들을 비교해주면 문제는 끝나게 된다.

지정 값과 밑의 줄의 첫번째 순서를 비교하는 논리는 위와 같다.

정리 하자면,

1) 비교 값(간식받을 번호)을 설정해주고 현재 줄(queue)의 첫 번째 순서와 비교

     -값이 같을 경우 pop, 다음 비교값 반복 

     -값이 다를경우 밑의 줄(stack)의 첫 번째 순서와 비교

          -값이 같을 경우 pop, 다음 비교값 반복

          -값이 다를 경우 현재 줄의 첫번째 순서를 밑의 줄로 옮김

2) 밑의 줄들을 비교 값(간식받을 번호)와 순서대로 비교하고 비교 값과 다를 경우 "Sad", 모두 같을경우 "Nice" 출력