Programmers Level2 조이스틱
돌파구
그리디 알고리즘은 간단하게, 문제해결을 위해서 수많은 선택을 거쳐야 한다고 했을 때 매 번 선택의 순간마다 더 좋은 또는 효율적인 것을 선택하는 알고리즘이다. 그래서, 지역적으로 만 최적화된 의사결정이다. 다른말로 하면, 전체적으로 봤을 때 더 좋은 선택이 있을수도 있다. 왜냐하면, 갈래길에서 그 순간에서만 좋은 선택을 했기 때문이다.
삶을 이루는 중요한 선택에서 왜, 나만을 위해 Greedy 하게 선택하면 안되는지.. 알려주는 알고리즘이다. 매 순간은 나의 이익을 취하는게, 나의 편함을 선택하는게 좋을지 모르지만, 길게 놓고 보면, 좋은 선택이 아니었다는 것을 후회하게 될 때. 나는 그리디(욕심적으로) 선택헀구나 라고 깨닫게 된다.
조이스틱문제는 의사결정 문제이다.
크게 두가지의 로직으로 나누었다.
1. 입력된 문자가 나올 때까지 위, 아래로 조작 할 때 드는 비용을 구하는 모듈
2. 입력된 문자를 완성하기 위해서 왼쪽, 오른쪽으로 조작 할 때 드는 비용을 구하는 모듈
여기서 왼쪽으로 갈지, 오른쪽으로 갈지를 선택하는 알고리즘이 그리디 알고리즘이 된다.
1.에서 구한 각각의 문자를 만들기 위해 조작해야 할 조이스틱의 비용이 담긴 배열을eachCost라고 하자. 그럼 이 배열의 0인 부분은 조작이 필요없는 부분이다. ('A' 는 조작할 필요가 없기 때문)eachCost를path에 복사하고 배열의 인덱스가 0인 지점이 조작을 시작하는 시작점 이므로 0을 집어넣는다. 이 배열의 모든 요소가 0이 될 때에 조작을 마친 것이다.- 매번
path.some(value => value !==0)을 통해서 배열이 0이 남아있을 때에는 아래 로직을 수행하도록 한다.
while 문 안의 로직
- toRight, toLeft 함수를 따로 빼내서 구현했다.
toRight함수는 오른쪽으로 이동할 떄 드는 비용과 조작해야할 인덱스를 리턴한다.toLeft함수는 왼쪽으로 이동할 때 드는 비용과 조작해야할 인덱스를 리턴한다.- 두 함수의 리턴값을 받아서 둘 중 작은 쪽으로 이동해서 조작한다.
구현
테스트 케이스 오류
사실, 이 문제에는 테스트케이스에 오류가 있다. console.log(joystick("BBBBAAAB") 일 때에는, 10이 맞는 답이지만, 위의 코드로 실행하면 12가 된다. 그렇지만, 프로그래머스의 모든 테스트 케이스는 통과한다.
pathIdx = leftLength <= rightLength ? leftIndex : rightIndex; 둘의 최소비용이 같으면 왼쪽으로 가도록 코드를 수정하면 위의 테스트케이스는 10으로 통과하지만, 프로그래머스의 11번 테스트 케이스는 통과하지 못 한다.
