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

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

 

 

 

TIL

• 여러 개 항목을 신경써야하는 경우, 독립적으로 계산하기 (커서 이동 횟수, 알파벳 변경 횟수 각각 따로)
• 동적으로 최솟값을 찾아야 하는 경우, 기준을 생각해보기
  • 단어의 길이에 따라 다른 경우, 중간을 기준으로 각각 Min값 처리가 달라질 수 있음
• 한 번 선택한 경우 or 순서대로 처리하는 경우, 다시 고려하지 않아도 됨  > Greedy
  • 한 번 지나간 문자의 경우, 다시 되돌아가지 않아도 됨 (어차피 왼-오 순서로 처리 + 각 문자별 변경 횟수 독립적임)

 

Code

def find_opt(char):
    return min(abs(ord(char)-ord('A')), abs(ord('Z')-ord(char))+1)

def solution(name):
    ans = 0
    n = len(name)
    cur = n-1
        
    # 커서 이동도 각 라운드마다 왼쪽으로 갈지, 오른쪽으로 갈지 최적화 해줘야함
    # 이렇게 하려면 방문여부에 대한 배열을 따로 작성해야하고, 더 번거로움
    # 처음부터 오른쪽으로 전부 이동하는 배열을 초기값으로 지정 > 오른쪽 방향 이동을 가정
    # 각 문자마다 왼쪽 방향으로 이동하는 값과 현재 cur 값 비교 후 더 작은 값 선택
    # 3번째까지는 오른쪽 갔다가, 그 뒤로는 왼쪽으로 갈 수도 있으니까
    # 중간에 A가 끊겨서 여러개있다해도(JAADFAADV) 어차피 한 번은 그냥 넘어야돼서
    # 아래와 같이 식 짜도 됨
    # min(i, n-next_i)인 이유는 중간을 기준으로 앞부분, 뒷부분일 때 이동 다름
    # 앞부분일때는 앞부분에서 뒤로 이동하는 게 더 빠름
    # 뒷부분일때는 뒷부분에서 앞으로 이동하는 게 더 빠름
    # 이런 식으로 동적으로 위치에 따라 값 바뀌는 경우에 인덱스 설정해두고 min하면 됨
    for i, c in enumerate(name):
        ans += find_opt(c)
        next_i = i+1
        
        while next_i<n and name[next_i]=='A':
            next_i += 1
        
        cur = min(cur, i + n - next_i + min(i, n - next_i))
    
    ans += cur
    return ans

 

 

Future works

DP로 풀 수 있나 확인해보기 (최적화가 불가능했던거 같음)