[Kotlin/프로그래머스/Lv.2] 조이스틱

 

https://programmers.co.kr/learn/courses/30/lessons/42860?language=kotlin 

코딩테스트 연습 - 조이스틱

https://taesan94.tistory.com/38  - 참고 (많이 참고)

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

 

문제

 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동

 예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

 만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

name                                                                                                      return

"JEROEN"	56
"JAN"	23

 

해결과정

 

 이틀을 고민하면서 풀었던 문제. 본인은 BFS를 사용하여 아주 복잡하고 어렵게 풀었는데, 문제 풀이를 보니 산수만으로도 매우 간단하게 풀 수 있었던 문제여서 좌절.. BFS밖에 생각나지 않았던 나에게 실망.. 그래도 풀었다는 거에 의미를 두고..앞으로 더 발전해 나가리라 믿는다.

 

1. [위,아래] 최소 이동거리 구하기.
   
   [위,아래] 이동은 철자를 바꾸는 조작이다. 문자는 'A' 부터 시작하기에 'A'를 주어진 문자와 같게 만드려면
   
   1. 'A'-'B'-'C'- .. -'주어진 문자' 와 같이 위로 이동하거나,
   2. 'A'-'Z'-'Y'-'X'-..-'주어진 문자' 처럼 아래로 (역순으로) 이동하는 방법이 있다.
   
   두 방법 중 제일 적게 이동하는 방법을 택하여 이동거리를 구한다. 
   
   주어진 문자를 val C 라고 한다면
   
   C - 'A' 는 'A'에서 위로 이동했을 경우 거리
   'Z' - C + 1 은 'A'에서 아래로 이동했을 경우 거리를 의미한다.('Z'-C : Z에서 C까지의 거리 , +1: 'A'에서 'Z'로 이동)
   
   따라서 철자를 바꾸기 위한 최소 이동거리를 구하기 위해서 C-'A' 와 'Z'-C+1 중  값이 작은 것을 선택하면 된다.
   
   
2. [좌,우] 최소 이동거리 구하기
   
   [좌,우] 이동은 인덱스를 이동하는 조작이다. 문자열 내에서 움직인 거리를 체크한다. 
   
   1. 기본 이동거리는 첫번째 인덱스부터 정방향 순서대로(우측) 문자열 끝 인덱스 까지 움직인 거리이다.
   
   val Min = name.length
   
   2.다음은 [우측 이동하다가 좌측으로 이동한 경우] 거리이다. 
   
    예를 들어, "BBAAAAB" 라는 문자열이 있다. 바꿔야할 문자는 0,1,6번째 문자 'B' 이다. 만약 1번 처럼 순서대로 이동한다면 바꾸지 않아도 되는 'A'들을 거쳐가기 때문에 +4 거리추가 동선 낭비가 발생하여 총 이동거리 = 6
   
    따라서 바꿔야할 0~1번째 까지만 우측 이동을 하고, 좌측 이동을 하여 곧바로 끝 인덱스로 이동한다면 (1번째 인덱스에 Back한 거리 = +1,  0번째 인덱스에서 끝 인덱스로 이동한 거리 = +1) +2 거리가 추가되어 총 이동거리 = 3 
   
   
   이처럼 좌측 이동이 더 거리가 짧은 경우를 구해주기 위해 반복문을 활용한다.
   
   1.인덱스 0부터 'A'가 시작되는 인덱스를 찾는다.
   
   "BBAAAAB" -> 2번 인덱스부터 'A' 시작. val start
   
   2. 'A'가 시작되는 인덱스(start)를 찾았다면 해당 인덱스부터 어느 인덱스까지 'A'가 연속되는지 인덱스를 늘려가며 카운팅한다.
   
   "BBAAAAB" -> 2번 인덱스부터 5번 인덱스 까지 연속된다.
   
   3.'A'의 연속이 끝나는 인덱스가 끝 인덱스(end) 가 된다.
   
   "BBAAAAB" -> 5번 인덱스에 끝. val end
   
   --이제 'A'가 연속되는 문자열을 지나지 않는 이동거리를 구하자. ("연속되는 'A'의 시작지점 전"까지 이동하였다가 다시 거꾸로 가는 경우의 이동거리)
   
   Min = math.min(Min, (start-1)*2 + (name.length - 1 - end))
   
   4. (start-1) 은 'A'가 시작하기 전 인덱스를 의미한다. 즉 0에서부터 시작 'A' 전까지의 거리가 된다.
   
    "BBAAAAB" -> 1번 인덱스에 위치한 'B'를 가리킴. 
   
   5.(start-1) * 2는 뒤로 back한 거리를 의미한다. 예를 들어 1번 인덱스에서 좌측이동을 하여 다시 0번 인덱스로 돌아가야 한다. 즉 start-1 만큼의 거리를 다시 돌아가야 한다. 즉, 와리가리친 거리니까 (start - 1) *2 가 된다. 
   
    "BBAAAAB" -> B에서 B로 갔다가, 다시 B에서 B로 가는 거리
   
   6.name.length - 1 - end 는 name의  끝 인덱스에서  'A'연속 문자열의 끝 인덱스를 뺀 값이다. 이는 맨 마지막에서 좌측이동 할 때 'A'가 끝나는 지점까지의 거리를 의미한다. 
   
    "BBAAAAB" -> B에서 거꾸로 돌아서 B를 거쳐 A인덱스까지의 거리
   
   7.따라서 "BBAAAB" 에서는 
   
   BB 를 왔다갔다하는 거리 (start-1)*2 = 2 ,
   0번 인덱스에서 거꾸로 A 까지 가는 거리 name.length - 1 -end = 1
   
   총 3 이동거리를 갖게 된다.
   
   
3. 1,2번 단계에서 구한 [상,하,좌,우]  모든 거리를 더하면 정답이 된다.
   
   

+ 추가한 점

"BBAAAA" 일 경우, 실제로 [좌,우] 이동이 "우측 이동 1번" 만 있어도 되지만, 위의 단계로 진행할 경우, BB에서 바보같이 돌아오느라 2번이나 이동하는 사태가 발생. 따라서 [상,하] 이동까지 합쳐 최종 이동거리가 4가 되버린다. (원래는 3이되어야 함) -> 프로그래머스 테스트 케이스에서도 잡아내지 못해서.. 그냥 통과해버린다.

그래서 [좌,우] 운동 단계에서 만약 'A'의 연속된 문자열이 name의 끝 인덱스까지 도달한다면 ("BBAAAA"처럼.) 뒤로 돌아갈 필요가 (좌측 이동을 할 필요가) 없기 때문에 (+우측이동을 할 필요도 X)  (start-1)이 [좌,우] 최종 이동거리가 된다.

소스 코드

class SolutionJoyStick2 {
    fun solution(name:String) :Int {
        var answer = 0

        //name의 각 철자들이 되려면 'A'로 부터 [위, 아래] 중 어느 방향으로 움직여야 더 가깝게 이동할 수 있는지 체크하고, answer에 더해줌
        for(i in name.indices) {
            val char = name[i]
            //'A'에서 char까지 걸리는 거리 = char - 'A'
            //'A'에서 거꾸로 돌아 'Z'로 간다음 char까지 걸리는 거리 = 'Z' - char + 1 (+1은 'A'에서 'Z'로 한 번 이동한 거리)
            if(char == 'A') continue
            answer += if(char - 'A' > 'Z' - char + 1) 'Z' - char + 1 else char - 'A'
        }

        //만약 단순히 [오른쪽]으로만 이동했다면 이동 거리는 name의 길이가 된다.
        var Min = name.length-1

        // [오른쪽] 으로 이동하다가 '연속되는 A'가 있어서 (낭비되는 동선) [왼쪽]으로 이동했을 시, 이동거리를 구한다.
        var start = 0

        while(start<name.length) {
            var idx = start
            if(name[idx]=='A') {
                while(idx<name.length && name[idx]=='A') idx++

                //start-1 : 'A'를 발견한 위치에서 뒤로 한칸 = 0에서 'A'까지의 거리
                //(start-1)*2 : 0에서 start-1 까지 왔다가, 다시 0으로 돌아간 거리.
                //(name.length-1) - idx : name의 끝 인덱스에서 start지점에서 연속된 'A'문자열의 마지막 인덱스를 뺀다. = 0에서 거꾸로 돌아서 이동한 거리.

                //+ 만약 idx가 name.length와 같다면 - 뒤로 돌아갈 필요가 없다.
                if(idx == name.length) Min = Math.min(Min, start-1)
                else {
                    var tmp = (start-1)*2 + (name.length-1) - (idx-1)
                    Min = Math.min(Min, tmp)
                }

                start = idx
            } else start++
        }


        answer += Min
        return answer
    }
}

fun main() {
    val solutionJoyStick = SolutionJoyStick2()

    println(solutionJoyStick.solution("BBAAAA"))
}