위대한 모험

면접 대비

시간 제한1초메모리 제한1024 MB

요약

아이템과 악당이 적힌 문자열을 읽고, 스택으로 처리했을 때 모든 악당에게 알맞은 아이템을 주고 가방을 비울 수 있는지 판정합니다.

난이도: 쉬움10점 중 3점
유형: 스택, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

용사 짐이 위대한 모험을 떠나려 한다. 가는 길에 돈, 향, 보석 세 종류의 물건을 만난다. 물건을 만나면 짐은 항상 그것을 배낭에 넣는다. 길에서는 악당도 만난다. 돈을 요구하는 은행가, 향을 요구하는 상인, 보석을 요구하는 보석상이다. 짐은 악당을 만날 때마다 그 악당이 요구하는 종류의 물건 하나를 건네야 한다. 건네지 못하면 실패하고 모험은 끝난다. 배낭이 불편해서 짐은 가장 최근에 넣은 물건만 꺼낼 수 있다. 위에 있는 물건을 건네기 전까지 아래 물건은 꺼낼 수 없다. 짐은 목적지에 도착할 때 배낭이 비어 있기를 바란다. 끝까지 배낭에 물건이 남아 있으면 모험은 실패로 본다.

짐이 모험을 시작하기 전에, 모험을 끝까지 마칠 수 있는지 미리 알고 싶다.

입력

첫 줄에 모험의 수 n (1 ≤ n ≤ 5)이 주어진다. 이어지는 n개의 줄에는 각각 모험을 나타내는 문자열 a가 한 줄씩 주어진다. 문자열은 {$, *, |, t, j, b} 문자로 이루어진다. 문자열의 예는 다음과 같다.

....$...$...*..*...|...t...j..j...b..b...

각 문자의 뜻은 다음과 같다.

$는 돈
|는 향
*는 보석
t는 상인
j는 보석상
b는 은행가
.는 땅 (아무것도 없음)

문자열의 길이는 1 ≤ |a| ≤ 100이다. 배낭에 넣을 수 있는 물건의 개수에는 제한이 없다.

출력

각 모험에 대해 짐이 모험을 끝마칠 수 있으면 YES, 없으면 NO를 출력한다.

예제2

예제 1

입력

5
.$.b.|.t.*.j.................$$$$$bbbbb||....tt.....
.$.b.|.t.*.j..
................................
.......$....$......*....*.....|......t........j...j.....b..b........
...$.$.$..*..*..*...*..|..*..b.....*******...

예상 출력

YES
YES
YES
YES
NO

예제 2

입력

4
........$b...$$..t...*..*...j.........j...
.........*****jjjj...............|tj....
.$.|.*.$.|.*.$.|.*.j.t.b.j.t.b.j.t.b.
...$$..$$..$$..|..$$..b......b....t..bbbbbb.....j...

예상 출력

NO
YES
YES
NO