문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42860#
우선 이 문제는 탐욕법(그리디 알고리즘)으로 분류되어 있지만 더이상 탐욕법으로 풀 수 없는 문제가 되었다. 아마도 변경 이전의 문제는 도착한 문자를 기준으로 가장 가까운 문자를 차례대로 찾아 나가는 방식으로 풀었을 것으로 예상된다.
하지만 현재 테스트 케이스가 추가되고 지문도 최단 거리를 요구하는 문제로 변경되었다. 따라서 더이상 그리디 문제가 아니다.
문제 접근법 자체가 달라져버렸고 다른 풀이들을 확인해 보았으나 대부분의 경우 완전 탐색을 통해 풀이하고 있었다. 사실 제한 사항을 확인해보면 문자열 자체가 20개 이하로 주어지기 때문에 완전 탐색으로 최단 경로를 찾아도 일반적인 코딩 테스트 기준에서 시간 초과가 나오지 않게 풀이할 수 있다. 만약 코딩 테스트를 치루고 있다면 그냥 완전 탐색으로 풀기를 바란다.
하지만 필자는 최소 시간으로 문제를 해결하기 위해 새롭게 알고리즘을 고안했다. 키 포인트는 문자와 문자 사이에 'A'만 존재하는 가장 긴 구간을 찾는 것이다. 이 구간만 탐색할 수 있으면 해당 구간 때문에 이동 방향을 바꾸는 경우를 상수 시간에 해결할 수 있다. 그런데 이제 이 구간을 탐색하는데 O(n) 시간이 소요되므로 전체 알고리즘의 시간 복잡도는 O(n)이라고 할 수 있겠다. 정리해보자면 다음과 같다.
-
모든 알파벳을 변경하는 횟수를 계산
-
수정할 알파벳을 방문하는 최단 거리를 계산
2-1. 첫 번째 문자부터 순차적으로 다음 'A'가 아닌 문자까지의 거리를 계산
2-2. 시작 문자부터 앞뒤로 'A'가 아닌 문자까지의 거리를 계산
2-3. 문자와 문자 사이에 'A'만 존재하는 가장 긴 구간[a,b] 중에 시작 지점에 더 가까운 (예를 들어)a 를 선택
2-4. 시작 지점에서 a까지의 거리 dist와 a부터 b까지를 멀리 돌아가는 거리 len(name) - dist_max를 합한 값을 저장
2-5. 2-4의 값을 순회하는 경우와 비교해서 더 짧은 경우를 선택 -
변경 횟수와 최단 거리의 합을 반환
def solution(name): answer = 0 alpha = 'A' * len(name) for i in range(len(name)): if alpha[i] != name[i]: diff = abs(ord(alpha[i]) - ord(name[i])) answer += diff if diff <= 13 else 26 - diff dist_list = [] dist = 1 for i in range(1, len(name)): if name[i] != 'A': dist_list.append(dist) dist = 0 dist += 1 dist_list.append(dist) start_dist = [dist_list[-1], dist_list[0]] dist_max = max(dist_list) reverse_list = dist_list[::-1] right = dist_list.index(dist_max) left = reverse_list.index(dist_max) right_sum = start_dist[1] for i in range(1, right): right_sum += dist_list[i] left_sum = start_dist[0] for i in range(1, left): left_sum += reverse_list[i] if left_sum > right_sum: dist = right_sum else: dist = left_sum if dist + len(name) - dist_max > len(name) - max(start_dist): answer += len(name) - max(start_dist) else: answer += dist + len(name) - dist_max return answer
