[프로그래머스] 조이스틱 - Greedy

프로그래머스 고득점키트 그리디 조이스틱 레벨2

 

• 완성해야 하는 문자열이 주어지고, 맨 처음에는 문자열의 길이만큼 A가 존재함
• 상하로 움직이면 현재 알파벳의 이전 또는 이후 알파벳이 나옴, 좌우로 움직이면 각 문자 사이 커서 이동
• 일단 상하로 움직여서 알파벳을 바꾸는 건 간단함
  • 파이썬 같은 경우에는 ord(알파벳)하면 아스키값을 알 수 있음
  • 그래서 ord('A') 또는 ord('Z')값과 각 문자열의 값을 뺄셈해서 절대값을 구하고, 둘 중 작은 값을 고름
  • 대신 주의해야될 것은 기본 값이 A이기 때문에 Z에서 시작하려면 A->Z로 변환하는 단계가 필요해서 1 더함
  • 그래서 A에서 아래로 움직여서 해당 알파벳으로 가는게 나은지?
  • 아니면 A에서 위로 움직여서 Z로 바꾼 후, 계속 위로 움직여서 해당 알파벳으로 가는게 나은지?
• 그다음에 이 문제에서 제일 빡치는 부분인 커서 이동을 구하면 됨
  • 위에까지는 금방 짰는데 이 부분은 결국 자료 참고해서 풀었음
  • 일단 가장 기본적인 첫 번째 알파벳부터 시작해서 오른쪽으로 한칸씩 이동하는 방법 = len(name)-1
  • 여기에서 관건은 A가 연속된 부분을 찾는거
  • 문자열의 알파벳을 하나씩 훑어봅시다
    • 현재 알파벳에서 인덱스를 하나씩 증가시켜가면서, 다음 인덱스가 문자열 길이를 넘지 않으면서 'A'인 경우
      • 그럼 현재 위치에서 A 직전까지 오른쪽으로 이동하는 것과 같음
      • 현재 위치 i에서 1씩 증가시켜서 포지션을 이동시켜본다
      • 현재 위치+1의 문자가 A라면 A 연속 문자열이 끝나는 지점을 next_idx에 저장
        • A의 왼쪽 위치에서 시작
          • i는 연속된 A 문자열의 왼쪽임.
          • 일단 A 문자열 왼쪽까지 감. (i만큼 이동)
          • 다시 처음으로 돌아오면서 역순으로 하나씩 바꿈(i만큼 이동)
          • 첫 번째 위치에서 끝 위치로 이동
          • 끝 위치에서 역순으로 연속된 A 문자열의 오른쪽 지점까지 이동(n-next_idx)
        • A의 오른쪽 위치에서 시작
          • i는 연속된 A 문자열의 왼쪽 위치
          • 일단 시작점에서 왼쪽으로 움직여서 끝에서 부터 역순으로 이동
          • 시작점에서 왼쪽으로 이동해서 연속된 A 문자열의 오른쪽 위치까지 이동(n-next_idx)
          • A 문자열의 오른쪽 위치에서 다시 오른쪽으로 이동해서 시작점까지 돌아옴(n-next_idx)
          • 시작점에서 i까지 이동하며 나머지를 바꿔줌(i만큼 이동)
    • 그냥 순서대로, A의 왼쪽부터, A의 오른쪽부터
      • 이 세가지 값 중에 MIN 값이 답임

def solution(name):
    answer = 0
    a_ord = ord('A')
    z_ord = ord('Z')
    # print(a_ord)
    # print(ord('Z'))
    arr = []
    # A에서 이동하는게 나은지? Z에서 이동하는게 나은지?
    for i in name:
        temp = ord(i)
        # print(abs(a_ord-temp), abs(z_ord-temp)+1)
        arr.append(min(abs(a_ord-temp), abs(z_ord-temp)+1))
    answer = sum(arr)
    n = len(name)
    
    # 커서 이동 구하는 부분
    move = n-1
    for i in range(n):
        next_idx=i+1
        while next_idx<n and name[next_idx]=='A':
            next_idx+=1
            # print(next_idx)
        # i 위치까지 왔다가 다시 돌아가서 가장 마지막 A가 아닌 문자까지 가는 경로
        # print(move, i+n-next_idx+i,i+2*(n-next_idx))
        move = min(move, i+n-next_idx+i,i+2*(n-next_idx))
    answer+=move
    
    return answer