[Python/프로그래머스]조이스틱_Greedy(그리디)

 

 

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

코딩테스트 연습 - 조이스틱

 

 

---

 

 

 

 

코드 : 

def solution(name):

	# 조이스틱 조작 횟수 
    answer = 0
    
    # 기본 최소 좌우이동 횟수는 길이 - 1
    min_move = len(name) - 1
    
    for i, char in enumerate(name):
    	# 해당 알파벳 변경 최솟값 추가
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        
        # 해당 알파벳 다음부터 연속된 A 문자열 찾기
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
            
        # 기존, 연속된 A의 왼쪽시작 방식, 연속된 A의 오른쪽시작 방식 비교 및 갱신
        min_move = min([min_move, 2 *i + len(name) - next, i + 2 * (len(name) -next)])
        
    # 알파벳 변경(상하이동) 횟수에 좌우이동 횟수 추가
    answer += min_move
    return answer

 

 

 

 

 

2가지를 생각해야한다.

 

 

1) 알파벳 변경

 

ord는 문자를 유니코드 정수로 반환해준다.

이를 이용해 'A'에서 움직이는 것이 빠른지, 'Z'에서 움직이는 것이 빠를지 비교하여 최솟값을 구한다. 

 

 

 

2) 위치 변경 

참고블로그(2)에 가면 그림이 있다.

왼쪽에서 오른쪽으로만 이동할 경우와 A가 나올 때까지 이동했다가 반대로 이동하는 경우를

비교해 최솟값을 찾는다는 것이다. 

 

 

 

 

잘 이해가 안되서 프로그래머스 -> 다른 사람풀이에서 이 댓글을 보고 이해했다.  (참고블로그(3)) 

 

 

- 1. 바로 오른쪽으로 가는 경우

 

 < 2 *i + len(name) - next > 

 

 

 

-2 . 바로 왼쪽으로 가는 경우 

 

문자의 끝으로 가서 먼저 뒷부분을 한 후에 앞으로 온다. 

 

 < 2 * (len(name) -next) + i >

 

 

 

 

 

 

 

 

 

참고 블로그 : 

 

https://velog.io/@jqdjhy/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1-Greedy

[프로그래머스, 파이썬] 조이스틱, Greedy

 

https://bellog.tistory.com/152

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

https://programmers.co.kr/learn/courses/30/lessons/42860/solution_groups?language=python3 

프로그래머스

 

 

복습 : 

 

✅ 20220622

✅ 20220624

✅ 20220626

✅  20220630