문제
N개의 서로 다른 문자들이 차례로 주어질 때,
이 문자들을 스택에 어떤 방법으로 넣고(push) 꺼내는(pop)가에 따라 다른 문자열이 얻어진다.
예를 들어 ABC 세 문자가 주어질 때, 이 문자를 스택에 넣고 꺼내는 방법을 달리한 결과
다음과 같은 문자열이 생성된다.
ABC : push(A), pop(), push(B), pop(), push(C), pop()
ACB : push(A), pop(), push(B), push(C), pop(), pop()
BAC : push(A), push(B), pop(), pop(), push(C), pop()
BCA : push(A), push(B), pop(), push(C), pop(), pop()
CBA : push(A), push(B), push(C), pop(), pop(), pop()
순열과는 다르게 CAB는 만들어지지 않는다는 점에 유의한다.
문자열 개수 N( 1 <= N <= 36 )과 문자열이 주어질 때,
문자열이 사전편집상 오름차순으로 몇 번째 스택 문자열인지 찾아보자.
N이 의미하는 바는 문자열 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"의
첫 문자부터 연속된 N개의 문자를(들을) 사용했다는 것이다.
예를 들어, N = 3 인 경우 사용된 문자열은 "012" 이고,
N = 6 인 경우 사용된 문자열은 "012345" 이다.
입력
첫 행에 테스트 케이스의 수 T( 1 <= T <= 100,000)가 입력된다.
다음 T개의 행에 N( 1 <= N <= 36 ) 과 문자열S가 공백을 구분하여 주어진다.
문자열 S에 등장하는 임의의 한 문자는 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ 중 하나이며
문자열 길이는 36을 초과하지 않는다.
출력
각 테스트 케이스에 대하여 문자열 S가 사전편집상 오름차순으로 몇 번째 스택 문자열인지 구하여 행으로 구분하여 출력한다.
주어진 문자열이 N개의 문자들로 얻을 수 있는 스택 문자열이 아닌경우 -1을 출력한다.
예제
10
3 012
3 102
7 0AB1234
6 01234
5 0123456789A
5 21043
11 368975421A0
4 3102
8 67543210
10 1032547698
1
3
-1
-1
-1
30
52375
-1
1429
5340
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.