시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (하단 참고) | 256 MB | 493 | 116 | 70 | 35.000% |
영어 알파벳 대문자로만 구성된 문자열이 N개 있다 (S[1], S[2], ..., S[N] 이라 칭하자).
Reverse(T)는 임의의 문자열 T를 뒤집은 문자열 이라 하자 (명백히, 모든 문자열 T에 대해 Reverse(Reverse(T)) = T 이다).
가령 Reverse("ABC") = "CBA" 이다.
당신은 N개의 문자열 각각에 Reverse() 함수를 적용할지 말지 고를 수 있고, 이를 통해 문자열이 사전순으로 정렬되도록 하고 싶다 (문자열이 N개 이므로 2N 가지의 방법이 존재한다).
각 문자열에 Reverse() 함수를 적용한 경우를 '1' 적용하지 않은 경우를 '0'으로 나타내면, 길이가 N인 0-1문자열이 된다 - 이를 "리버스 문자열" 이라 하자. (리버스 문자열은 길이가 N인 0-1 문자열이다).
예를 들어 N = 3이고 S[1] = "ABC", S[2] = "XC", S[3] = "DZ" 라 하자.
이 외에도 다른 방법으로 세 문자열을 사전순으로 정렬할 수 있다.
입력으로 주어진 N개의 문자열을 사전순으로 정렬하는 리버스 문자열이 항상 존재한다는 가정하에, 그러한 리버스 문자열 중 사전순으로 가장 앞서는 리버스 문자열을 출력하시오.
첫 줄에 테스트 케이스의 수 T가 주어진다.
테스트 케이스의 첫 줄에 문자열의 수 N이 주어진다.
다음 N줄에 걸쳐 한 줄에 하나씩 영문 알파벳 대문자로만 구성된 문자열이 주어진다.
각 테스트 케이스에 대해 조건을 만족하는 리버스 문자열 중 사전순으로 가장 앞서는 리버스 문자열을 출력한다.
2 3 ABC ABD XY 3 ABC XC DZ
000 001
사전식 순서: 두 문자열 S, T가 주어졌을 때 S가 T의 prefix 이거나 혹은 S와 T를 비교했을 때 처음으로 다른 문자 (알파벳)가 각각 s, t인 경우 s가 t보다 사전순으로 앞서는 경우 S가 T보다 사전순으로 앞선다고 한다.