[Algorithm] Programmers : 조이스틱 by Python

엄희관·2020년 11월 30일
0

Algorithm

목록 보기
17/128
post-thumbnail

[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/42860

📌문제 설명

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

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

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동
예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다.

  • 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
  • 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
  • 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
    따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
    만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

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

입출력 예 )

💡 문제 풀이

문제 설명만 보면 간단해보이나 조건이 명확하지 않아서 문제가 많았던(?) 문제였다... 실제로 질문하기 페이지에서도 혼란을 겪은 사람들이 많았다 ㅎㅎ

먼저 내가 문제를 잘못 이해한 것(으로 추정되는...)은 오른쪽 커서였다.

첫 번째 위치에서 왼쪽(◀)으로 이동하면 마지막 문자로 커서가 이동한다고 명시되어 있어서 오른쪽(▶)도 동일한 기능이 존재할거라 생각했는데 해당 내용이 없었기 때문에 통과!!

다음으로 혼란을 겪은 것은 커서의 첫 위치였다.

예시에서는 첫 번째 문자부터 시작했지만 반드시 첫 번째 문자부터 시작해야한다는 말이 없어서 처음에는 위아래 조작이 가장 적은 문자위치부터 시작했으나 다른 사람의 질문을 참고하여 무조건 첫 번째 위치부터 시작하였다.
근데 해당 내용은 나만 혼란이 온 것 같았다...


다시 본론으로 들어가서 '조이스틱' 문제를 풀기위해 아래와 같이 작성하였다.

check 함수
left : 왼쪽방향 인덱스
right : 오른쪽방향 인덱스
cnt : 이동거리

"A"는 위아래 조이스틱 위아래 조작이 필요없기 때문에 "A"를 마주쳤을 때 조이스틱 조작 최소화를 위한 이슈가 발생!

따라서, check 함수는 조이스틱의 왼쪽(◀) 오른쪽(▶) 방향을 결정짓기 위한 함수로서 "A"가 나타난 지점부터 왼쪽 오른쪽 방향으로 움직였을 때 가장 먼저 조작이 필요한 문자("A"가 아닌 문자)가 나타나면 위치(idx)와 이동 횟수(cnt)를 return한다.

answer : 조작횟수의 최소값
step : 위아래로 조이스틱 조작시 최소로 움직이는 횟수를 담은 리스트

def check(idx, step):
    left = right = idx # 왼쪽방향 index | 오른쪽방향 index
    cnt = 0
    while True: #"A"가 아닌 문자가 나올 때 까지 반복한다.
        right += 1
        left -= 1
        cnt += 1
        if right == len(step): # 오른쪽 끝 위치에 도달하면 고정 
            right = len(step)-1
        if left  == -1: # 왼쪽 끝 위치에 도달하면 오른쪽으로 끝 이동
            left = len(step)-1
        if step[right]: # 오른쪽 방향에 문자가 나타나면 인덱스, 횟수 return
            return right, cnt
        if step[left]: # 왼쪽 방향에 문자가 나타나면 인덱스, 횟수 return
            return left, cnt
            
def solution(name):
    answer = 0
    step = [0] * len(name)
    # 위아래 조이스틱 조작 최소값은
    # "A"부터 문자까지의 거리와 "Z"부터 문자까지의거리 + 1 중 최소값이다.
    for i in range(len(name)):
        step[i] = min(abs(ord("A")-ord(name[i])), abs(ord("Z")+1 - ord(name[i])))

    idx = 0
    while sum(step):
    	# "A"가 아닌 문자일 경우 위아래 조이스틱 조작
        if step[idx]:
            answer += step[idx]
            step[idx] = 0
        # "A"가 나타날 경우 왼쪽, 오른쪽 방향 결정(check 함수)
        else:
            idx, cnt = check(idx, step)
            answer += cnt + step[idx]
            step[idx] = 0
    return answer

문제를 풀고 마지막 위치에서 오른쪽방향으로 이동했을 때 첫번째 위치로 오도록 코드를 수정해보았는데 똑같이 통과하였다...
아무래도 보다 정확한 문제 조건의 제시가 필요할 것 같다...

profile
허브

0개의 댓글