문제
N개의 다이얼이 연결된 자물쇠를 돌려서 풀어야 하는데 다이얼 중 하나를 골라 1번 돌리는 작업을 해야 하는데, K번을 돌려서 나올 수 있는 단어 중에 가장 사전순으로 앞인 단어를 찾으면 된다.
내가 가진 정보는 자물쇠의 길이 N과 작업의 횟수 K 그리고 다음 줄에는 문자열 S가 주어진다 해당 문자열에서 돌려서 가장 사전순으로 작은 문자열을 만들면 된다.
예제를 보자.
4 3
ABCD
의 경우, 3번을 돌려 나올 수 있는 사전순으로 가장 작은 단어는 ABCG이다. ABC는 어차피 사전순으로 가장 앞이므로 D를 세번 돌려 D → E → F → G를 만들었다.
4 5
XYZW
해당 문자열은 XYZW가 AAZW로 변했다. X → Y → Z → A Y → Z → A 로 총 5번을 돌렸다.
이를 통해 가장 앞인 문자부터 검사해서 돌려서 만약 알파벳 앞 순위의 숫자로 변환할 수 있다면 변환하는 것을 알 수 있다. 그리디 알고리즘이 이에 대해 가장 잘 맞는 알고리즘같다.
- 앞문자열부터 하나씩 검사
- 알파벳의 아스키코드를 더했을 때 이전보다 사전순으로 앞인 알파벳이 나오면 더한다.
- 없으면 뒤로 돌린다
- 마지막에 남은 횟수를 다 돌린다. 정도로 생각할 수 있다.