210925 토 Algorithms TIL

https://bong-f.tistory.com/268

프로그래머스

조이스틱

• 코드

나의 풀이

• 먼저 알파벳을 해당 하는 알파벳을 만들어 두고 이동할 거리를 구했다.
• 최적의 거리를 구하는 방법은 어디서 이동하든 다음 목적지로 갈 때 최선으로 이동한다고 생각했다. 그래서 해당 목적지에 도달할 때까지 순차적으로 가는 방법과 거꾸로 가는 방법 두가지 케이스로 나눠 최적의 거리를 구했다.

    def getlength(p, to) :
        if(p <= to):
            return min(to - p, p + 1 + lastidx - to)
        else :
            return min(p-to, lastidx - p + 1 + to)

• 그리고 하나의 기점에서 앞쪽 방향의 a가 아닌 것으로 가는 것이 더 가까운지 뒤쪽 방향의 a가 아닌 것으로 가는 것이 더 가까운지 계산하여 구했다.
• 그렇게 하기 위해서는 a가 아닌 인덱스를 만들어둘 필요가 있었다. 하나하나 순회하면서 찾는 것이 아니라 해당 인덱스로 바로 이동해서 확인할 수 있게끔

다른사람 풀이

• 해당 풀이 설명 : https://bellog.tistory.com/152
• 좀 더 쉬운 풀이를 찾아봤다. (아래) 결국 고려할 것은 어떤 점에서 시작할지를 정하고 / 그 점에서는 경우의 수가 2가지로 나뉜다. 한 번에 쭉 갈 것인지, 바로 옆에 a가있어서 그 a를 건너지 않고, 다시 back해서 거꾸로 돌아 뒤돌아서 갈 것인지. 그래서 나올 수 있는 경우의 수는 알파벳의 길이 * 3 이 것들의 경우의 수만 구하면 된다.
• 내가 매번 최선으로 구했을 때랑 둘 다 정답인 것이 신기하다.
• A가 연속인 값을 가장 큰 것을 구해서 그곳을 지나지 않고 (거꾸로 가서 돌아와 길을 반복하더라도) 가는 방법과 지나서 일자로 가는 방법 중에 최소를 구하는 것