๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜ ๐Ÿ’ก/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์กฐ์ด์Šคํ‹ฑ Greedy

by @ENFJ 2024. 9. 1.

  
name return
"JEROEN" 56
"JAN" 23
def solution(name):
# ์กฐ์ด์Šคํ‹ฑ ์กฐ์ž‘ ํšŸ์ˆ˜
answer = 0
# ๊ธฐ๋ณธ ์ตœ์†Œ ์ขŒ์šฐ์ด๋™ ํšŸ์ˆ˜ : ๊ธธ์ด - 1
min_move = len(name) - 1
for i, char in enumerate(name): # enumerate() ํ•จ์ˆ˜: enumerate()๋Š” ๋ฐ˜๋ณตํ•  ๋•Œ ์ธ๋ฑ์Šค์™€ ๊ฐ’์„ ๋™์‹œ์— ์ œ๊ณตํ•˜๋Š” ํ•จ์ˆ˜์ž…๋‹ˆ๋‹ค. enumerate(๋ฐ˜๋ณต_๋Œ€์ƒ)์€ (์ธ๋ฑ์Šค, ๊ฐ’) ํ˜•ํƒœ์˜ ํŠœํ”Œ์„ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
#์•ž์œผ๋กœ ์ด๋™ํ•˜๋Š” ๊ฒฝ์šฐ
forward_move = ord(char) - ord('A')
#๋’ค๋กœ ์ด๋™ํ•˜๋Š” ๊ฒฝ์šฐ
backward_move = ord('Z') - ord(char)+1
# ํ•ด๋‹น ์•ŒํŒŒ๋ฒณ ๋ณ€๊ฒฝ ์ตœ์†Ÿ๊ฐ’ ์ถ”๊ฐ€
answer += min( forward_move, backward_move )
# ํ•ด๋‹น ์•ŒํŒŒ๋ฒณ ๋‹ค์Œ๋ถ€ํ„ฐ ์—ฐ์†๋œ A ๋ฌธ์ž์—ด ์ฐพ๊ธฐ
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