프로그래머스 2단계 - 조이스틱

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.

 

ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

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

 

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

 

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

---

제한 사항

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

---

입출력 예

---

접근법 1

1. A B C ... K L M N = 0, 1, 2 ... 10 11 12 13
   Z Y X ... P O = 1, 2, 3, ... 12
   딕셔너리 형태로 저장한다.
2. 각 문자를 key 값으로 받아서 value값을 리턴해준 후 더한다.

alphabet = {'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}

def solution(name):
    name_ = list(name)
    answer = 0
    for i in name_: # name을 하나씩 i에 넣어준다.
        if i in alphabet:# name이 alphabet에 있다면
            answer += alphabet[i]
            if i != 'A': # A가 아니라면 마지막 문자로 위치 이동 시킨다.
                answer +=1
    answer -= 1 # 맨 마지막 문자는 위치 이동 하지 않는다.
    return answer

 

문제를 제대로 이해하지 못한 50점짜리 풀이이다. 

출제 의도와도 맞지 않으며 "AAA"를 넣으면 -1이 출력된다.

 

접근법 2

1. 종료조건 base에 ‘A’를 name 갯수까지 만들고 모든 name을 A로 치환할 때까지 반복한다.
2. 아스키코드값을 이용하여 해당 index에 다음 알파벳으로 움직일지, 이전 알파벳으로 움직일지 정한다. (알파벳 26개중 절반값을 이용)
3. 해당 index의 알파벳을 바꾼 결과가 종료조건에 만족하지 않을시 커서 이동방향을 찾는다.
4. 커서는 왼쪽, 오른쪽 따로 이동해가며 ‘A’가 아닌 값이 나올때까지 반복한다. 여기서 먼저 ‘A’가 아닌값이 나오는 방향을 선택

 

def solution(name):
    list = [min(ord(s) - ord('A'), ord('Z') - ord(s) + 1) for s in name]
    
    answer = 0
    locat = 0

    while 1:

        answer += list[locat] 
        list[locat] = 0

        if sum(list) == 0: break
        
        left = 1
        right = 1

        while list[locat + right] == 0:
            right += 1

        while list[locat - left] == 0:
            left += 1
            
        if left >= right:
            locat += right
            answer += right

        else:
            locat -= left
            answer += left

    return answer

 

이 조이스틱은 두가지를 최적의 방법으로 정해야한다.

 

첫번째는 문자의 이동이다.

▲ 방향키를 사용해서 원하는 문자로 이동을 할지 

▼ 아래 방향키를 사용할지 정해야 한다.

 

알파벳은 총 26자이므로 A에서 14번째 존재하는 알파벳은 ▲ 방향키보다 ▼ 방향키로 이동하는 것이 더 효율적이기 때문이다.

이는 아스키코드 함수인 ord를 사용해서 이동하고 그 차이만큼 answer에 더하도록 한다.

 

두번째는 위치의 이동이다. 문자 중 A가 존재한다면 문자를 이동시킬 필요가 없으므로 왼쪽으로 이동할지 오른쪽으로 이동할지 결정을 해야한다.

 

방금 문자를 이동시킨 인덱스에서 오른쪽 문자와 왼쪽 문자 중 A가 아닌 것을 더 빨리 만나는 쪽으로 이동하도록 하였다.

 

두가지 방법을 원하는 알파벳을 만들때까지 반복하면 된다.