25204번 - 문자열 정렬 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 232 | 88 | 52 | 41.935% |
문제
Bob은 문자열 정렬기를 만들어야한다.
문자열은 영문 알파벳 이외에도 붙임표 ('-')가 들어가는 경우가 있기 때문에 처리가 까다롭다. 이 문제에 한해, 서로 다른 두 문자열 $X$, $Y$의 "사전식" 순서는 아래 규칙에 따라 정한다:
- $X$가 $Y$의 접두사인 (prefix) 경우 $X$가 $Y$보다 앞선다. 반대로, $Y$가 $X$의 접두사인 경우 $Y$가 $X$보다 앞선다.
- 위 경우에 해당하지 않을 경우: 첫번째 문자부터 시작하여 $X$, $Y$가 처음으로 달라지는 부분이 $i$번째 문자라 하자. $X$의 $i$번째 문자를 $X_i$, $Y$의 $i$번째 문자를 $Y_i$라 했을 때:
- 둘 중 하나만 붙임표 ('
-')인 경우, 붙임표가 들어간 문자열이 사전순에서 뒤진다. 예를 들어, $X_i$가 붙임표이고 $Y_i$가 붙임표가 아닌 경우, $Y$가 앞선다. - 둘 다 알파벳인 경우, 대소문자를 무시했을 때 서로 다른 알파벳이라면, 알파벳 순서를 따른다. 만약 같은 알파벳이지만 하나만 대문자인 경우 대문자가 들어간 문자열이 사전순에서 앞선다.
- 둘 중 하나만 붙임표 ('
예를 들어, 아래와 같은 문자열 쌍을 비교해보자:
- $X = $"
Santa-Mar" 과 $Y = $"Santa-Maria": 이 경우 규칙 1에 따라 $X$가 앞선다. $X$가 $Y$의 접두사이기 때문이다. - $X = $"
San-Francisco" 와 $Y = $"Santa-Clara": 이 경우 처음 $3$개의 문자는 같지만 $4$번째 문자가 '-'와 't'로 다르다. 규칙 2-1에 따라 $X$가 $Y$에 뒤진다. - $X = $"
Seoul"과 $Y = $"seoul": 이 경우 규칙 2-2에 따라 "Seoul"이 앞선다.
입력으로 $n$개의 문자열이 주어졌을 때, 위 규칙에 따라 사전식 정렬 후 출력하는 문자열 정렬기를 만들어보자.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $n$이 주어진다. 다음 $n$줄에 걸쳐 각 줄에 문자열이 하나씩 주어진다.
출력
각 테스트 케이스의 정답을 $n$줄에 걸쳐 출력한다. 각 줄에는 사전순으로 정렬된 문자열 하나씩을 순서대로 출력한다.
제한
- $1 ≤ T ≤ 10$
- $1 ≤ n ≤ 15\,000$
- 각 테스트 케이스의 입력으로 주어지는 $n$개의 문자열에 대하여:
- $1 ≤ $ 문자열의 길이 $ ≤ 50$
- 문자열은 영문 대문자 ('
A'-'Z'), 영문 소문자 ('a'-'z'), 그리고 붙임표 ('-') 만을 포함한다
예제 입력 1
4 3 Aa- a-A Aa- 7 San-Francisco Santa-Clara Santa-Clarita San-Luis-Obispo San-Pedro Saint-Paul Saint-Louis 2 Santa-mar Santa-Mar 3 - -- ---
예제 출력 1
Aa- Aa- a-A Saint-Louis Saint-Paul Santa-Clara Santa-Clarita San-Francisco San-Luis-Obispo San-Pedro Santa-Mar Santa-mar - -- ---
예제 1: "Aa-" 문자열이 두 번 주어졌으므로 두 번 출력해야 한다. "Aa-" 와 "a-A"를 비교하면 첫 글자가 다르므로 규칙 2-2에 따라 "Aa-"가 사전순으로 앞선다.
예제 2: "Saint-Louis" 와 "Saint-Paul" 의 경우 'L' 이 'P' 보다 앞선다.
예제 3: "Santa-Mar" 과 "Santa-mar"의 경우 'M' 이 'm' 보다 앞선다.
예제 4: 추가 설명 없음 (규칙 1 참고)
시간 제한
- Java 8: 2.5 초
- Python 3: 2.5 초
- PyPy3: 2.5 초
- Java 8 (OpenJDK): 2.5 초
- Java 11: 2.5 초
- Kotlin (JVM): 2.5 초
- Java 15: 2.5 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호