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

chanyeong kim·2021년 12월 17일

greedy 프로그래머스

프로그래머스

목록 보기

33/51

vue image

📩 -->문제설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.

조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.

마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한사항

name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.

입출력 예

name	return
"JEROEN"	56
"JAN"	23

💡 solution(사용언어: python)

import re
def solution(name):
    # 각 알파벳이 변환될 때 필요한 조작 횟수
    score={'A':0, 'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,'K':10,'L':11,'M':12,'N':13,'O':12,'P':11,'Q':10,'R':9,'S':8,'T':7,'U':6,'V':5,'W':4,'X':3,'Y':2,'Z':1}
    change=0
    for i in name:
        change+=score[i]
        
    # A가 연속된 부분이 있어 -> 방향으로 쭉 가거나 -> <- <- 이 방향으로 갈지 정해줘야 함
    startA = re.compile('[A]+')
    check = re.findall(startA, name[1:])  # 연속된 A를 담아줌
    cnt1=0
    if check:
        tmp = name[1:].split(max(check))
        if '' in tmp:
            cnt1=len(max(check))
        else:
            cnt2 = 2*len(tmp[0])+len(tmp[-1])
            cnt1=min(len(name)-1, cnt2)
            return change + cnt1
    
    # 알파벳 바꾸는데 키 + 오른쪽으로 쭉 가는 경우 - A가 연속되어 있다면 그냥 건너뛰는 경우
    return change+len(name)-1-cnt1

👉 설명

먼저 change에는 A가 name에 있는 알파벳으로 바뀔 때 필요한 조작횟수를 모두 담아준다.
(처음에 쉬운 문제라고 생각했던 부분이) 결국 change 에서 오른쪽으로 한칸 이동 할때마다 1번씩 조작 횟수를 추가해 주어야 하기 때문에 len(name)-전체길이 에서 1을 빼준 값을 더해주면 최소 조작 횟수라고 생각했다.
- 'BBAABBAAAAAAAAAB' 이런 문자열이 있고, 위 방식대로 하면, change(5) + 15로 20이 나온다
- 그런데 처음 ▶방향으로 BBAABB만큼 이동하고, 앞에 연속된 A가 많기 때문에 다시 ◀ 방향으로 BBAABB 이동한 후 마지막 문자인 B만 바꾸어 주게 된다면 총 조작횟수는 16이 나오게 된다.
그렇기 때문에 입력받는 문자열에서 연속된 A가 존재하는 문자열이 있는지, 있다면 ▶으로 쭉 갈것인지 ▶+◀+◀ 방향으로 갈것인지 정해주어야 했다.

먼저 정규표현식을 이용해서 연속된 A 문자열을 담아 주었다.

startA = re.compile('[A]+')
 check = re.findall(startA, name[1:])  # 연속된 A를 담아줌

연속된 A가 존재한다면, 연속된 A 문자열 중 가장 긴 문자열을 기준으로 split 해주었다.
가장 긴 A 문자열이 맨 마지막에 있다면, cnt1에 길이를 담아 주었다(▶ 방향으로 쭉 갈때 빼버려야 최소 조작 횟수이기 때문에)
- ```
if '' in tmp:
    cnt1=len(max(check))  
```
그렇지 않으면, ▶+◀+◀의 길이를 cnt2에 담아 주었다.
그리고 ▶로 쭉 갔을 때와 cnt2 중 작은 수를 cnt1에 담아준 후 change+cnt1을 return 해준다.
연속된 A가 중간에 없거나, 혹은 맨 마지막에 있는 경우는 그냥 change + len(name) - 1 - cnt1을 return 해준다.