https://www.acmicpc.net/problem/34051
문제요약
- N 길이의 문자열이 주어짐(소문자, 5000)
- 부분문자열을 최대 한 번 뒤집을 수 있음
- 만들수 있는 사전순으로 가장 큰 문자열 구하기
접근법
- 모두 시도해보면 좋겠는데 시간 복잡도가 찜찜하다 : O(N^3)
- 그런데 잘 생각해보면 N^3이 안걸림
- 문자열 왼쪽 위치부터 시작점으로 고려함 : 사전순으로 바꾸면 가장 이득이 되는 지점이니까
- 반대쪽 문자가 시작 문자보다 클때만 뒤집음 : ex) Z.....A 는 뒤집어도 의미가 없음
- 일단 뒤집을 수 있으면 그중에서 가장 사전순으로 뒤에 나오는 것이 답 : 그 다음 위치는 뒤집을 필요 없음
- 시간복잡도 : O(N^2)
- 다 뒤집어 보지 않고 : 시작<끝 일때만 뒤집음
- 그 이후 위치는 안 뒤집어도 되니까 : 문자열 왼쪽 위치부터 시작하기 때문에
newbieski