Level 2. 조이스틱

조이스틱

코딩테스트 연습 > 탐욕법 > 조이스틱

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

문제 설명

문제 구상

• 입력: 알파벳 대문자로 이루어진 문자열
• 과정:
  1. 'A' x len(입력값) 인 문자열로부터 입력값으로 변환되기 까지의 최소 횟수를 구하기 위해 initial value로 min_count(최소 변환)와 min_move(최소 이동)을 지정한다.
  2. 정방향으로만 움직이는 것이 아닌 양방향으로 움직이기에, 해당 부분을 고려한다.
     1) 정방향의 최소 이동 수(len(name)-1)와 역방향 최소 이동 수2 * 현재 위치+(len(name))-가까운 'A'의 위치의 최소값을 구해 min_move를 갱신한다.
     2) ord(n)-ord('A'),ord('Z')-ord(n)의 최소값을 구해 min_count에 추가한다.
  3. min_move+min_count 를 출력한다.

문제 풀이

# Input values
name = 'JEROEN'

# Set initial value : answer = min_count + min_move
min_count= 0
min_move = len(name)-1

for i,n in enumerate(name):
    next_ = i+1 # move to find position
    while next_ < len(name) and name[next_] == 'A':
        next_+=1 # Go to the next position
    min_count+= min(ord(n)-ord('A'),ord('Z')-ord(n)+1) # Select minimun transform
    min_move = min(min_move,2*i+len(name)-next_) # Select minimum move

min_count+min_move

역방향에 대한 고려방법이 어려워 다른분들의 풀이를 최대한 참고하여 작성했습니다.

전체 코드

def solution(name):
    min_count= 0
    min_move = len(name)-1

    for i,n in enumerate(name):
        next_ = i+1
        while next_ < len(name) and name[next_] == 'A':
            next_+=1
        min_count+= min(ord(n)-ord('A'),ord('Z')-ord(n)+1)
        min_move = min(min_move,2*i+len(name)-next_)
    return min_count+min_move