시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 1776 | 411 | 260 | 23.572% |
Windows의 파일 탐색기를 보면 파일이 정렬된 방식이 보통의 정렬 방식과는 다른 것을 알 수 있다.
보통 문자열을 정렬할 때는 맨 앞부터 한 글자씩 비교하다가 어느 한쪽이 끝나거나 일치하지 않는 글자가 있으면 그 위치의 문자를 비교한 결과가 문자열 전체를 비교한 결과가 된다. 한편 파일 탐색기는 여러 자리의 수를 한 글자로 취급해서 비교하는데, 이 때문에 "str12ing
"과 "str123ing
" 중 후자가 아니라 전자가 앞에 온다. 이러한 정렬 방식을 종종 "natural sort"라고 하기도 한다.
여러 개의 문자열이 주어지면 natural sort 방식으로 정렬한 결과를 출력하는 프로그램을 작성해 보자. 이 문제에서 구현할 알고리즘은 다음을 만족해야 한다.
a12bc345
"는 "a
", "12
", "b
", "c
", "345
"의 다섯 단위로 이루어져 있다.첫 줄에 문자열의 개수 N(2 ≤ N ≤ 10,000)이 주어진다. 그 다음 N줄에 정렬할 문자열이 한 줄에 하나씩 주어진다.
모든 문자열의 길이는 100 이하이며, 알파벳 대소문자와 숫자로만 이루어져 있다.
N줄에 걸쳐 문제에서 설명한 대로 문자열을 정렬한 결과를 출력한다.
8 Foo1Bar Foo12Bar Foo3bar Fo6Bar Foo00012Bar Foo3Bar foo4bar FOOBAR
FOOBAR Fo6Bar Foo1Bar Foo3Bar Foo3bar Foo12Bar Foo00012Bar foo4bar
5 1234567890123456789012345678901234500500 1234567890123456789012345678901234500000 1234567890123456789012345678901234506000 1234567890123456789012345678901234500002 1234567890123456789012345678901234530000
1234567890123456789012345678901234500000 1234567890123456789012345678901234500002 1234567890123456789012345678901234500500 1234567890123456789012345678901234506000 1234567890123456789012345678901234530000