[프로그래머스 LV2] 조이스틱

문제

잡담

직접 문제를 풀다가도 최적의 해가 맞는지 아닌지 계속해서 햇갈리는데, 테스트 케이스가 통과되서 놀랐다.

다른사람들 풀이도 보았는데, 실제로 못 써먹을 것 같아서 일단 내풀이로 작성!

누가 볼진 모르겠지만, 완벽한 풀이가 아니기 때문에 그냥 가볍게 보고 가시면 좋겠다!

접근방법

1. 먼저 ▲▼ 를 계산하는 것이 빠를것 같았다.
   ▲ 를 사용하는 경우는, 현재 위치(A) 를 바꿔야할 위치(target) 에서 빼주면 되고

   ▼ 를사용하는 경우는 , (알파벳의 길이 - 바꿔야할 위치) 를 사용해주면 된다.

   그리고, ▲▼ 중에서 가장 작은 값을 반환해야 하는 값에 더해준다.

   이를, 모든 이름의 알파벳을 확인할 때 까지, 더해준다.
   

2. ◀▶ 를 판단할 때, 오른쪽으로 순서대로 가면 좋겠지만,
   중간에 A 가 있으면, 왼쪽으로 돌아가는 것이 좋을 때가 있다.

   이를 판단하기 위해서, 이름의 위치 를 KEY 로 갖고
   ▲▼의 값 을 value 로 갖는 dict 를 생성해준다.
   

3. 현재 위치에서 다음 위치를 찾으면서,
   다음 위치로 이동이 왼쪽 , 오른쪽 중 가장 작은 값이 무엇인지 판단을해야한다.

   모든 이름들을 방문할때 까지 반복문을 반복하면서
   매 반복시마다, 다음위치를 찾는다.

   방문하지 않은 노드, A 가 아닌 노드, 현재 위치가 아닌 노드를 다음위치 후보군에 넣어준다.

   다음 위치 후보군에는, ◀, ▶로의 각각의 거리 값과 다음위치의 인덱스 값을 원소로 갖는 후보들을 넣는다.

   다음위치가 되는 것은 ◀, ▶로의 각각의 거리 값 중에서 작은 값의 가장 작은 값을 갖는 것으로 한다.

   반환되는 값에 다음위치의 ◀, ▶로의 각각의 거리 값 중 작은 값을 더해주고,

   다음위치 값을 방문 처리해주고, 현재위치를 다음위치의 인덱스 값으로 해준다.

4. 방문하지 않은노드가 있지만, 만약 후보군에 들어올 것이 아예 없으면, 그 값은 A 이기 때문에, 방문 처리를 해준다.

   (어차피, 반환되는 값에 더해지는 것은, 다음위치 ~ 현재위치 사이의 최소 거리 이기 떄문에 따로 처리해주지 않아도 된다)

   ---

   코드

   def solution(name):
      alphabet = [x.upper() for x in "abcdefghijklmnopqrstuvwxyz"]
      default_name = list('A' * len(name))
      target_name = list(name)

      length = len(target_name)
      count = 0
      dic = {}

      visit = [False] * length
      now_move = 0
      visit[now_move] = True

      for i in range(length):
          target_word = target_name[i]
          default_word = default_name[i]

          up = alphabet.index(target_word) - alphabet.index(default_word)
          down = len(alphabet) - alphabet.index(target_word)

          min_up_down = min(up, down % len(alphabet))
          count += min_up_down
          dic[i] = min_up_down

      while any([x == False for x in visit]):
          index_array = []
          for i in range(length):
              if visit[i] == False and dic[i] != 0 and i != now_move:
                  left = i > now_move and length - i + now_move or now_move - i
                  right = now_move > i and length + 1 or i - now_move
                  index_array.append((left, right, i))

          if len(index_array) > 0:
              next_move = min([x for x in index_array], key= lambda x: (min(x[1], x[0]), x[1], x[0]))
              count += (min(next_move[0], next_move[1]))
              visit[next_move[2]] = True
              now_move = next_move[2]

          else:
              for i in range(length):
                  if visit[i] == False and dic[i] == 0:
                      visit[i] = True


      return count