[프로그래머스] [Level 2] [완전 탐색] 조이스틱

조이스틱

프로그래머스

 

 

• 사이트에 그리디 문제로 나와있지만 테스트케이스 추가 후 그리디 방식으로는 해결 X
  • → 완전 탐색 방식 사용

참고 사이트: https://kjhoon0330.tistory.com/entry/프로그래머스-조이스틱-Python

 

• 다른 사람 풀이 (# 완전 탐색)
  • 가야할 곳은 'A'가 아닌 곳입니다. 
  • 따라서 'A'가 아닌 곳의 인덱스를 전부 찾은 뒤(시작 위치 제외) 해당 인덱스들을 모두 방문하는 모든 경우의 수, 즉 순열을 구합니다.
  • 각 순열에 따른 이동 거리를 구해보고 이를 가지고 정답을 갱신합니다.
  • 모든 순열 중 최소 이동 거리가 나온 것이 문제에서 요구한 정답이 됩니다.

 

• ord(문자) : 문자 → 10진수
  • ord('Z') -ord(alp) +1 : Z에 가까운 경우 A까지의 거리를 위해 Z에서 뺀 후 +1
  • ord(alp) - ord('A) : A에 가까운경우 
  • min() 함수로 그 중 작은 값 판별

from itertools import permutations as p

INF = int(1e9)

# 알파벳이 주어졌을 때 상하로 움직이는 횟수 구하는 함수
def countChange(alp):
	return min(ord('Z') - ord(alp) + 1, ord(alp) - ord('A'))

# 왼쪽, 오른쪽 중 최단으로 가는 거리 구하는 함수
def findShortestPath(name, now, next):
    right, left = max(next, now), min(next, now)
    rightDist = right - left
    leftDist = left + len(name) - right
    return min(rightDist, leftDist)

def solution(name):
    answer = INF
    # "A" 가 아니라서 가야하는 위치(시작 위치 제외)
    toGoPlaces = [i for i in range(len(name)) if name[i] != "A" and i != 0]

    # 알파벳을 바꾸느라 생기는 이동
    changeCount = 0
    for c in name:
        changeCount += countChange(c);

    # 움직일 수 있는 모든 케이스
    cases = p(toGoPlaces, len(toGoPlaces))
    for case in cases:
        now = 0
        result = 0

        for next in case:
            dist = findShortestPath(name, now, next)
            result += dist
            now = next
            
        answer = min(answer, result + changeCount)

    return answer

 

• 다른 방법
  • 리스트가 아닌 경우: list(reversed(~))
    • reversed( 튜플, 리스트, 문자열 ) 후에는 list() 를 써줘야함
  • reverse() 같은 경우는 리스트만 사용 가능 : list.reverse() 

#알파벳 찾아 상하로 움직이는 횟수
def countChange(alp):
    return min(alpha.index(alp), list(reversed(alpha)).index(alp)+1)

• list[::-1] 
  • 마지막부터 처음까지 -1하면서 역순 배열

#알파벳 찾아 상하로 움직이는 횟수
def countChange(alp):
    return min(alpha.index(alp), list(alpha)[::-1].index(alp)+1)