Programmers) Lv2 조이스틱

출처: https://programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱 | 프로그래머스

분류: Lv2, Greedy

---

너무너무 어려웠던 문제... 하 어렵네요 Greedy... 누가 Greedy가 제일 쉽다고 했나요 ㅠㅠ 
저처럼 어려웠던 분들 계시겠죠?? 같이 알아보겠습니다!

접근

어차피 결국 알파벳들을 맞춰야만 하니까 알파벳을 조작하는 횟수와 특정 알파벳으로 이동하는 횟수를 각각 구해주면 되겠다고 생각했습니다. 

알파벳 조작 횟수

몇 번을 움직여야 하는지 횟수만 알면 되기 때문에 Ascii 값으로 비교해서 횟수를 카운트 하면 되겠다 싶었고,
대신 거꾸로도 움직일 수 있기 때문에 특정 Ascii value - 65 가 절반인 13보다 크다면 거꾸로가 더 빠르기 때문에 이경우 26에서 빼줬습니다.

var cnt = Int(c.asciiValue!) - 65

if cnt > 13 {
	cnt = 26-cnt
}

 

이런식으로요!

 

이동 횟수

네 문제는 이녀석이였죠...

어리석은 제가 처음 했던 생각은

"첫번째 문자부터 시작하기 때문에, 처음에 오른쪽이든 왼쪽이든 방향을 결정하면 돌아올 일 없이 가장 최적이겠구나"

하지만, 오른쪽으로 진행하고 있어도 다시 반대로 돌아오는게 더 최적인 경우가 있습니다.
바로 "AABAAAAAAAB" 이런 경우인데요, AAB까지 갔다가 다시 거꾸로 돌아와서 맨 마지막 B를 해결하는게 더 최적이죠.. 

따라서 Greedy답게 오른쪽 왼쪽 중 고칠 필요가 있는 문자(A가 아닌 값)가 나올 때까지 이동해야 하는 횟수 중 더 적은 경우를 다음 이동방향으로 정해서 이동해야 최소의 이동횟수를 구할 수가 있습니다. 

풀이

저는 Swift는 문자열을 조작하기가 까다롭고 n이 최대 20밖에 안되기 때문에 처음에 알파벳 조작 횟수부터 카운트 하면서
Ascii 값을 담은 배열을 따로 만들고 0으로 초기화되어있는 배열이 Ascii 배열과 일치할 때 까지 while 문을 돌려서 해결했습니다.

이렇게 따로 하지않고 바로바로 비교해나갈 수도 있을거 같긴 하네요!

왼쪽 오른쪽 비교하는 부분도 최선인가 싶기도 하구요.. 정말 최적의 풀이는 아닌 것 같네요..ㅠ-ㅠ 

더 좋은 방법이나 개선할 부분이 있다면 알려주시면 감사하겠습니다 XD

func solution(_ name:String) -> Int {


    var nameAsciiArray = [Int]()

    // 모두 A이면 0
    if String(repeating: "A", count: name.count) == name {
        return 0
    }

    var count = 0

    // 글자 조정 횟수
    for c in name {
        var cnt = Int(c.asciiValue!) - 65

        if cnt > 13 {
            cnt = 26-cnt
        }

        count += cnt
        nameAsciiArray.append(cnt)
    }

    var myAsciiArray = [Int](repeating: 0, count: name.count)
    myAsciiArray[0] = nameAsciiArray[0]

    var idx = 0
    // 이동 횟수
    while myAsciiArray != nameAsciiArray {
        var right = idx
        var rCnt = 0
        while myAsciiArray[right] == nameAsciiArray[right] {
            right += 1
            if right >= name.count {
                right = 0
            }
            rCnt += 1
        }

        var left = idx
        var lCnt = 0
        while myAsciiArray[left] == nameAsciiArray[left] {
            left -= 1
            if left < 0 {
                left = name.count - 1
            }
            lCnt += 1
        }

        if rCnt <= lCnt {
            count += rCnt
            idx = right
        } else {
            count += lCnt
            idx = left
        }
        myAsciiArray[idx] = nameAsciiArray[idx]
    }


    return count
}