문제 링크
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
'개발 > algorithm' 카테고리의 다른 글
[프로그래머스][level2] 124 나라의 숫자 - python (0) | 2022.04.14 |
---|---|
[프로그래머스][level2] [1차] 프렌즈4블록 - python (0) | 2022.04.14 |
[프로그래머스][level2] 방금그곡 - python (0) | 2022.04.11 |
[프로그래머스][level2] N개의 최소공배수 - python (0) | 2022.04.11 |
[프로그래머스][level2] 이진 변환 반복하기 - python (0) | 2022.04.11 |