풀이_조이스틱.md

🐶 프로그래머스 조이스틱 풀이

• Date : 2020.08.15(토)
• Time : 60분 그 이상..
• 풀이 실패 ..

탐욕 알고리즘

• 탐욕 알고리즘은 최적해를 구할 때 사용하는 방법
• 그 상황에서 제일 좋은 방법들을 택해가면서 나간다
• 항상 3개지를 검사해야한다.

1. 선택작업 : 현 상태에서 최적해에 포함시킬 대안을 선택
2. 타당성 조사 : 선택된 해가 주어진 문제의 조건을 만족하는지 검사
3. 해답 조사 : 원래의 문제가 해결되었는지를 조사

내가 최대한 풀어서 맞은 풀이

• 항상 A에서 시작한다는 것을 바탕으로 위 아래 조작 키의 숫자를 다 구해주고 시작했다.

    for j in range(0,len(answerKey),1) :
        if ord(answerKey[j])-ord('A') <= ord('Z') - ord(answerKey[j]) :
            num[j] = ord(answerKey[j]) - ord('A')
        else :
            num[j] = ord('Z') - ord(answerKey[j]) + 1
    #Z에서 더 가까운 알파벳은 Z에서 빼줬고, 하지만 그렇게 된다면 아래 조이스틱을 한번 더 조작해야하기 때문에 +1을 해줬다.

: 이렇게 된다면 "JEOREN"은 [9, 4, 12, 9, 4, 13]로 변환된다. 이런식으로 풀이를 시도하니깐 반만 맞았다.

내가 생각하지 못한 point

• 조이스틱은 왔던 곳을 다시 돌아올 수 있다.
• 0('A')이 있다고 무조건 다른쪽으로 돌아가는 것이 아니다.
• 0('A')들의 사이에 알파벳에 껴있을 수 있다.

옳은 풀이

1. A가 아니면 위 아래 조작 횟수를 구해서 answer에 더해준다.
2. 그 다음 그 알파벳은 A로 바꾼다.
3. 양 옆에 알파벳을 조사해서 A를 넘어서 다른 곳으로 가려면 얼마나 조작해야하는지 숫자를 센다.
4. 왼쪽 수, 오른쪽 수를 비교해서 더 작은 수로 가서 그 만큼 조작 횟수를 answer에 더해준다.
5. 그리고 그 만큼 index값도 더해준다.
6. 반복한다.
7. 모두 A면 끝난다.
   : 조이스틱_해답.py