문제링크 : http://acm.kaist.ac.kr/Problems/2003oc.pdf
ACM-ICPC 2003년 온라인예선 C번



-----------------------------------------------------------
뭐 풀이는 테스트 케이스에서는 문제 없이 돌아가지만 어떤 예외상황에선
문제가 있을지도..;;

먼저
BEER와 DRINK를 예로 들자면
어제 고민 했을때처럼 알파벳 순으로 숫자를 표기하고(어짜피 아스키값으로 비교할꺼기 때문에..)

먼저 BEER같은경우 1223, DRINK는 15243로 번호를 매긴다
그리고 뒤에서부터 한자리씩 비교
15243과 15243 비교!
뒷자리가 작으므로 패스
다시 15243과 15243을 비교
뒷자리가 크다!
그러면 이제 여기서 STOP
4의 앞자리인 2와, 4의 뒷자리에 있는 모든 수를 비교한다
지금은 3밖에 없으므로 일단 3과 비교
(만약 뒤로 수가 많다면 2보다 큰 수 중에 가장 작은수랑 바꾸야 한다)
3이 크다 그러면 이제 3과 2의 자리를 바꾼다
그러면15342
하지만 여기서 끝이 아니다
가운데 자리(처음에 2가 있었던 자리 뒷부분) 뒤쪽으로는
오름차순 정렬!(버블소트든 퀵소트든 상관없음)
그러면 15324 <-이런식으로 바꾸면 DRKIN 정답!
그럼 끝 BEER같이 뒷자리 R뒤에 숫자가 없거나 E보다 큰수가 없으면 그냥
R과 E 자리만 바꾸면 된다

소스코드 :


by 알 수 없는 사용자 2007. 6. 26. 00:25