[완전탐색] Level2 프로그래머스 조이스틱 진짜 정답 풀이(그리디는 안됨)

프로그래머스 조이스틱 자바(java) 풀이

• Level 2
• 조이스틱
  
  
  

먼저 이야기하자면 이 문제는 그리디로만 풀어야만 답으로 인정해줍니다.
물론 완전탐색으로 풀어도 TC 모두 정답이 나옵니다. 하지만 문제를 제대로 풀기 위해서는 완전탐색으로 풀어야 합니다.
그리디는 아무데서나 쓰는 것이 아니라했는데 여기서 확실히 깨닫습니다...
예시는 아래에서 이야기하겠습니다!!

문제 정리

1. 기본 문자열은 길이가 몇이든 A로만 이루어져 있다.
2. 위, 아래로 조이스틱을 움직이면 알파벳을 변경할 수 있다. 위로 이동하면 A->Z로 이동가능하다.
3. 아래로 이동하면 Z->A로 이동가능하다. 만약 A에서 아래로 이동한다면 'Z'가 된다.
4. 왼쪽, 오른쪽 키는 커서를 움직여 다른 문자위치로 움직일 수 있다.
5. 이때 주어진 문자열을 만들기 위해 움직여야 하는 최소 조작 회수를 구하여라.
   
   
   

Greedy 풀이(Solution)

이 풀이가 통과는 하지만 정답을 내지는 못합니다. TC가 좀 빈약합니다.
오른쪽으로 가다가 왼쪽으로 가는 경우 제대로된 값이 나오지 않습니다.
이는 solution 함수로 구현하였습니다.

1. 문자를 바꿔야 한다면 위로 바꾸는게 빠른지, 아래로 해서 바꾸는게 빠른지 확인합니다. 더 적은 방향으로 이동합니다.
   min(arr[idx] - 'A', 'Z' - arr[idx] + 1)
2. 그리고 문자를 바꾸려는 문자로 바꿔줍니다. 같아졌다면 탐색을 그만둡니다.
3. 왼쪽, 오른쪽으로 A가 아닌 문자를 찾습니다. 더 적게 이동가능한 쪽으로 이동합니다. 이때 0보다 작아지거나 길이보다 커지는 경우 index를 조정합니다.
   0보다 작아지는 경우 길이를 더해줍니다.
   배열의 끝 인덱스보다 큰 경우 길이로 나눠줍니다.
   
   
   

완전탐색 풀이(Solution2)

"CANAAAAANAN"와 같은 경우 greedy로 풀면 정상적인 답을 내지 못합니다.
TC를 추가하여 계산하면 프로그래머스에서 원하는 답으로 50이 나옵니다. 문제가 문제가 좀 많습니다...
진짜 greedy 방식으로 풀어서 나온 답만 인정하고 있습니다. (첫 번째 위치에서 왼쪽으로 이동시 문자 끝으로 이동가능)
0 -> 1 -> 2 -> 1 -> 0 -> 10 -> 9 -> 8 인덱스로 이동하면 48이 맞습니다.
그렇기 때문에 이와 같은 완전탐색 풀이로 모든 경우를 탐색하여야만 48이라는 답을 낼 수 있습니다.
이는 solution2 함수로 구현하였습니다.

1. 왼쪽으로 쭉 가는 경우
2. 오른쪽으로 쭉 가는 경우
3. 오른쪽으로 갔다가 왼쪽으로 가는 경우
4. 왼쪽으로 갔다가 오른쪽으로 가는 경우
   위의 모든 경우를 따져 줘서 가장 작은 조작 횟수를 구하면 됩니다.
   
   
   

프로그래머스 조이스틱 자바 코드