프로그래머스 조이스틱 그리디

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 이하입니다.

입출력 예

namereturn

"JEROEN"	56
"JAN"	23

---

풀이: 

이게 왜 그리디인지 모르겠다. 그냥 빡구현 아닌가? 어쩌면 빡구현이라고 느끼는건 내 내공 부족일 수도 있겠다. 

주어진 초기설정 = AAAA (0 <l en(초기설정) < 21) 에 대하여 한칸씩 이동하며 알파벳을 조정하여 타겟 ex) ZABC 과 동일하게 만드는데 가장 적은 시간이 드는 경우를 return 하면 된다. 

 

두가지 기능이 필요하다. 

1) A 에서 타겟 알파벳으로 변환 

이건 사실 간단하다. 다들 ord 함수를 쓰는데, 난 이상하게 ord 함수를 그렇게 쓰기가 싫다. 그냥 단순 integer 거리 계산이면 끝난다. 

 

2) 자리이동 

자리 이동의 경우 처음부터 끝까지 쭉 이동할 수도 있지만 타겟 알파벳이 A 인 경우 조정이 필요 없으므로 

AAAAAAAB 의 경우 오히려 반대로 가면 1번만 이동해도 해결이 된다. 

 

문제는 이러다 보니 가다 돌아오는 경우를 상상하면 정말 어떻게 나올지 감이 안왔다. 

하지만 잘 생각해보면 가다 멈추고 돌아온다는 것은 멈춘 위치 다음 위치까지 반대로 돌아서 온다는 것이다. 

B C A A A A A A A D G A  의 경우 C 에서 멈추고 반대쪽은 D 까지 오면 되므로 중간의 A 를 무시한다 할 때 바로 옆 원소이다. 

 

대부분 사람들의 풀이를 추후 점검해보면 다들 C ~ D 사이에 A 는 무시하며 cnt를 직접하는 걸 볼 수 있었다. 

다만 나는 복잡한 걸 싫어하는 편이라 일을 나눠서 처음에 알파벳의 index를 찾을 때 A 를 제외하고 다른 알파벳의 위치만 list에 저장을 해 두었다. 

B C A A A A A A A D G A

idx_lst(구현 코드에서는 tmp_lst): [1, 2, 10, 11]

와 같이 말이다. 

그 결과 2와 10의 위치만 비교해서: for i,j in zip(idx_lst, idx_lst[1:] + [0])

 

왼쪽으로 가다 돌아가는 경우: i * 2 + 총 길이 - j 

오른쪽으로 가다 돌아가는 경우: (총 길이 - j) * 2 + i 

 

로 좀더 보기 편하게 해결 했다. 

 

하지만 항상 그렇듯 나만의 방법으로 머리를 써서 풀면 생각 못한 예외 케이스에서 문제가 생긴다. 

 

# 문자가 A 만 있는 경우 

# 문자 한개 

# CA, AC 

 

문자가 A 만 있으면 아예 idx_list에 추가가 안되어서 max, min 연산에서 에러가 발생한다. 

해당 문제는 len(idx_list) == 0 일때 바로 답을 return 해버려서 해결한다. 

 

문자가 한개만 있는 경우는 3경우로 나뉘는데 바로 

1) 한개만 있는 경우 ex) B, C, D ..

2) 문자 한개 뒤에 A만 나오는 경우 ex) CAAA, BAAAAAA, DA ..

3) A 뒤에 문자 한개만 붙는 경우 ex) AAAAC, AAAAAAB, AAD, AAADAA, ADAAA... 

 

1, 2 번 경우는 답을 바로 return 해버리면 깔끔하나, (움직일일이 없다.)

 

3번의 경우 해당 답 까지 이동하는 거리를 계산해야 해서 스킵할 수 없다. 

그때는 

밑에 처럼 1,2 번 경우만 바로 return 하도록 하게 하거나 

혹은 3번의 경우를 고려해 idx 값(움직인 거리)를 더하도록 해서 해결한다. 

 

그렇게 어려운 문제가 아닐텐데 내게는 어려웠다. 다시 만났을 때 예외 처리를 잘 할 수 있을까? 

이상이다. 

 

def solution(name):
    alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    answer = 0
    tmplst = []

    for idx,i in enumerate(name):
        tmp = alpha.find(i)
        if tmp == 0:
            continue 
        answer = answer+tmp if tmp <  len(alpha)-tmp else answer+len(alpha)-tmp
        tmplst.append(idx)
        
    #문자가 A 만, 문자 한개, CA, AC 
    if len(tmplst) == 0 or (len(tmplst) == 1 and tmplst[0] == 0):
        return answer
        
    
    a = max(tmplst); b = len(name) - min(i for i in tmplst if i > 0)  
    c = len(name) + 1; d = len(name) + 1
    
    for i,j in zip(tmplst, tmplst[1:] + [0]):
        c = min(i * 2 + len(name) - j, c)
        d = min((len(name)-j)*2 + i, d)
    
    answer = answer + min(a,b,c,d)
    
    print(a,b,c,d)
    
    return answer