개발/algorithm
[프로그래머스][level2] 조이스틱 - python
zzi_on2
2022. 4. 11. 23:49
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42860
코딩테스트 연습 - 조이스틱
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다
programmers.co.kr
풀이 - 다른 블로그 참고
- 이해가 잘 안돼서 다른 블로그 글을 참고해서 풀었다 .. !
+ 2022.04.21. 다시 풀이. 완전히 이해
- 연속되는 A의 최대 거리가 핵심.
변경하는 알파벳마다 가장 긴 연속되는 A를 찾고, 왼쪽부터 시작하는 것과 오른쪽부터 시작하는 것과 그냥 일직선으로 가는 것의 이동 횟수를 구해 최솟값을 갱신한다.
1. 처음 왼쪽에서부터 오른쪽으로 쭉 일직선으로 가는 이동 거리
2. 가장 긴 연속되는 A의 왼쪽에서 시작하는 이동 거리
3. 가장 긴 연속되는 A의 오른쪽에서 시작하는 이동거리
알파벳마다 위 3가지 이동거리를 비교해 좌우 이동 거리의 최솟값을 갱신해주고, 마지막에 answer에 더하면 된다.
def solution(name):
answer = 0
n = len(name)
# 기존 왼쪽에서 오른쪽으로 이동 거리
min_move = n
for i in range(len(name)) :
# 위 또는 아래로 조작하여 알파벳 완성 최솟값
answer += min(abs(ord(name[i])-ord('A')), abs(ord('Z')- ord(name[i]) +1))
next = i + 1
# 연속되는 A의 최대 길이 구하기
while next < n and name[next] == 'A':
next += 1
# 일직선으로 가는 것, 연속되는 A의 왼쪽에서 시작에서 이동, 연속되는 A의 오른쪽에서 시작해서 이동하는 것의 최솟값
min_move= min(min_move, i + i + n - next, 2*(n-next) + i )
# 최소 좌우 이동거리 더하기
answer += min_move
return answer