문제

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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

설명

바로 눈 앞의 상황을 판단하여 제일 효율이 좋은 판단을 내리는
'탐욕법(그리디 알고리즘- greedy algorithm)'을 사용하여 푸는 문제 입니다.

그리디 알고리즘을 개념을 몰라서 좀 많이 헤맸던 기억이 납니다... 정말 괴상한 방법들을 많이 썼습니다.

왼쪽 오른쪽 리스트를 만들어 알파벳 변경 수치까지 낮은 값으로 진행하도록 코드를 짜보기도 하고, 조이스틱 커서가 -1이면 다시 최대 수치로 변경하지 않나...

하지만 맞췄을 때 코드는 정말 단순 했습니다. 위의 로직들은 다 불필요 하더라구요.

그럼 거두절미하고 제가 찾은 규칙부터 설명 드리겠습니다.

1) 첫번째 값(그러니까 리스트로 따지면 index 0번이죠)은 A가 아니면 무조건 수정하고 시작한다.

2) 그 뒤로 조이스틱 커서의 위치를 좌우로 확인하여 A가 아닌 값을 찾는다. A일 경우 한 단계 더 넘어가 값을 찾으며, 양쪽 다 A가 아닌 값을 찾았을 때 좌우의 거리 중 가까운 쪽을 선택한다.

3) 알파벳을 바꿀 때는 (조이스틱 위 아래) B와 Z는 한 번, C와 Y는 두 번 필요하다. 이렇게 따져 나갔을 경우, N이 한 가운데 값이며 총 13번을 입력해서 바꿔야 한다.

4) 현 위치의 알파벳을 3번 규칙대로 바꾸고 다시 2번으로 돌아가 프로세스를 반복한다.

위의 규칙에 맞게 코드를 작성하시면 됩니다.

일단 제가 푼 코드를 먼저 올리고 추가 설명을 진행하겠습니다.

from string import ascii_uppercase
def solution(name):
    alpha_dict = dict(zip(list(ascii_uppercase), [idx for idx, _ in enumerate(ascii_uppercase)]))
    alpha_dict["A"] = -999
    text_ls = [abs(alpha_dict[c]) if alpha_dict[c]<abs(alpha_dict[c]-26) else abs(alpha_dict[c]-26) for c in name]
    cursor = 0
    answer = 0
    while True:
        # A가 아니면 계산
        if text_ls[cursor] != 999:
            answer += text_ls[cursor]
            text_ls[cursor] = 999
        # 탈출 조건
        if text_ls.count(999) == len(text_ls):
            break
        #기본 커서 생성
        tmp_direction = [1,1].copy()
        tmp_right = cursor + 1
        tmp_left = cursor - 1
        # 오른쪽 커서 판별
        while text_ls[tmp_right] == 999:
            tmp_right += 1
            tmp_direction[1] += 1
        # 왼쪽 커서 판별
        while text_ls[tmp_left] == 999:
            tmp_left -= 1
            tmp_direction[0] += 1
        # 좌우 값 비교
        if (tmp_direction[1]) <= (tmp_direction[0]):
            cursor = tmp_right
            answer += tmp_direction[1]
        else:
            cursor = tmp_left
            answer += tmp_direction[0]
    return answer

저는 알파벳을 다루는 로직을 짠 게 아닌 알파벳에 1~13~1 의 값을 부여하여 '변경해야 하는 횟수'의 리스트로 구축 후, 이후 로직은 전부 숫자로 다루도록 변경했습니다.

또 A는 999로 입력하여 다른 알파벳과 구분할 수 있도록 만들어놨습니다. 아래에 주구장창 튀어나오는 999는 해당 커서의 위치 값이 A인지 판별하고 있는 셈입니다.

뱀발로 설명드리자면, ascii_uppercase 함수는 알파벳 대문자가 들어가있는 문자열 그 자체입니다. 소문자를 가져오고 싶으면 ascii_lowercase를 호출하면 됩니다.

~~사실 문자열로 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"를 선언해서 써도 되긴 합니다...~~

리스트 구축은 다음과 같이 진행했습니다.

1) ascii_uppercase로 대문자 문자열을 가져오고, zip을 통해 {<알파벳>:<순서값>}으로 이루어진 딕셔너리 구축합니다.

2) A의 값을 -999로 입력(이는 나중에 절대값 변경을 활용하려고 만들어놨습니다. 3단계를 거쳐 999로 변경됩니다)

3) 알파벳 딕셔너리에 input 값의 문자 하나하나씩 대입해 순서값을 가져오면서, 26을 뺀 절대값 보다 작으면 그 순서 값을 입력(절대값을 씌워놔 -999도 처리합니다)하고 그게 아닐 경우 26을 뺀 절대값을 가져오도록 합니다.

예시를 들자면 Z의 번호는 25번이 될 텐데, 거기에 26을 뺀 절대 값은 1입니다. 그렇다면 기존 번호인 25번이 26을 뺀 값보다 더 커지게 될테니 Z는 25 대신 1로 바꿔서 입력 되겠죠?

이렇게 알파벳을 변경에 필요한 횟수로 변환한 다음, 좌우 이동시키는 것만 로직을 짜고 나머지는 해당 리스트의 값을 더해서 구했습니다. (물론 999는 무시하고 넘어갑니다.)

생성한 리스트의 값들은 각 알파벳으로 바꿀 때 필요로 하는 횟수 일테니까요.

사실 이렇게 까지 복잡할 필요는 없는데 저 알파벳 딕셔너리를 만드는 부분이 마음에 들어서 그대로 블로그에 올리기까지 진행했습니다.

더 효율적이고 획기적인 방법이 있다면 언제든지 피드백 주세요~!

이 블로그 검색

폐기물 저장소

Programmers) 조이스틱

문제

제한 사항

입출력 예

설명

댓글

댓글 쓰기