프로그래머스 Lv. 2 Swift 알고리즘 - 조이스틱_그리디

3일만에 알고리즘 문제를 풀었는데... 거의 2주만에 푼 느낌..? 그리고 매일 풀다가 3일 쉬니까 죄짓는 느낌이 들었다.

이제부터 알고리즘 유형에 맞게 문제를 풀어보려고 하는데 처음부터 상당히 문제를 푸는데 오래걸렸다 ㅠㅠ

그리디 유형의 문제인데 그리디는 아무리 이론을 이해하고 있어도 막상 풀 때 적용시키는 것과는 또 다른 문제가 있는 것 같다.

 

A 상황에서 가장 최적의 방법을 선택 -> B 상황으로 이동 -> B 상황에서 가장 최적의 방법을 선택 -> ...

이런 식의 개념으로 접근하였는데 역시나 예상 외의 변수를 전부 생각하지 못했는지 틀리고 말았다!

 

그래서 구글링하여 코드를 참고하였다 ^^...

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 우선 A - Z 까지 Character끼리 값을 비교하는 것은 굉장히 불편하기 때문에 각 알파벳마다 값을 부여한다.
2. A라면 값을 바꾸지 않아도 되니 0이라고 가정하고 Z는 25의 값을 갖는다.
3. 각 위치와 상관없이 (위 / 아래) 버튼을 이용하여 알파벳을 바꿔주어야하는 경우는 고정적으로 발생하기 때문에
4. 값이 0인 원소를 제외하고 모든 값들을 전부 더해준다.
5. 값이 0인 원소가 있을 경우 이제 위치를 움직여줘야하는데
6. 첫 번째 위치에서 시작했을 때 오른쪽으로 가는 것과 왼쪽(맨 끝에서 다시 시작)으로 가는 것 중 어떤 방식이 덜 움직이는지 파악한다.
7. 이를 idxR, idxL로 기록하여 몇칸 움직였고 현재 위치가 어디인지를 파악한다.
8. 이렇게 위치가 바뀐 경우 시작했던 자리를 0으로 만들어주고 다시 새로운 위치에서 좌, 우 값을 사용하여 최소 길이의 위치를 찾는다.
9. 이를 반복하면 끝
10. 하지만 내 코드는 뭔가 오류가 있었다...
11. 그래서 코드를 참고했는데 내가 생각했던 방식과 비슷하게 푼 분들은 2022년 1월 이후로 개정된 테스트 케이스를 맞추지 못한 분들이 많았다.
12. 그래서 또 찾아보니까 이를 해결한 분이 계셨는데... 왼쪽, 오른쪽 한계점을 기준으로 왕복 거리를 이용한 분이셨다... 솔직히 이건 생각도 못했다... 오늘도 한 수 배워 갑니다...

 

 

* 처음 틀린 코드

import Foundation

func solution(_ name:String) -> Int {
    let alphabet = (97...122).map({Character(UnicodeScalar($0)).uppercased()})
    var dict: [String : Int] = [:] // 알파벳에 값을 붙여 몇칸 이동해야하는지 확인
    var compare: [Int] = []
    var idx: Int = 0 // 현재 위치
    var moveCount: Int = 0
    var ans: Int = 0
    
    for (j,i) in alphabet.enumerated() {
        dict[i] = j
    }
    
    for i in name {
        compare.append(dict[i.uppercased()]! > 13 ? 26 - dict[i.uppercased()]! : dict[i.uppercased()]!)
    }
    
    if !compare.contains(0) {
        ans = compare.reduce(0, +) + compare.count-1
    } else {
        ans = compare.reduce(0, +)
        
        for _ in 0...4 {
            var idxR: Int = 0 // 오른쪽으로 몇 칸?
            var idxL: Int = 0 // 왼쪽으로 몇 칸?
            
            // 몇 칸이나 가는지 돌려보자... 오른쪽
            for i in 1... {
                // 헛돌기 시작하면 끝내주자
                if i >= compare.count {
                    break
                }
                
                if compare[(idx + i) % compare.count] == 0 {
                    continue
                } else {
                    idxR = i
                    break
                }
            }
            
            // 몇 칸이나 가는지 돌려보자... 왼쪽
            for i in 1... {
                // 헛돌기 시작하면 끝내주자
                if i >= compare.count {
                    break
                }
                
                if compare[abs(compare.count - i + idx) % compare.count] == 0 {
                    continue
                } else {
                    idxL = i
                    break
                }
            }
            
            // 더이상 없으면 탈출
            if idxR == 0 && idxL == 0 {
                break
            }
            
            compare[idx] = 0
            
            // 오른쪽이 더 많이 움직였다면? -> 왼쪽으로 가는게 낫다!
            if idxR > idxL {
                idx = abs(compare.count - idxL) % compare.count
                moveCount += idxL
            } else {
                idx = (idx + idxR) % compare.count
                moveCount += idxR
            }
        }
        ans += moveCount
    }
    return ans
}

 

 

* 참고한 코드

import Foundation

func solution(_ name:String) -> Int {
    let name = name.utf8.map{ min(Int($0) - 65, 90 - Int($0) + 1) }
    let countUD = name.reduce(0, +)
    var countRL = name.count - 1
    
    let idx = 0
    for idxR in 0..<name.count {
        var idxL = idxR + 1
        while idxL < name.count && name[idxL] == 0 {
            idxL += 1
        }
        let compareDistance = min(idxR - idx, name.count - idxL)
        countRL = min(countRL, (idxR - idx) + (name.count - idxL) + compareDistance)
    }
    
    return countUD + countRL
}

 

 

정리(Today I Learned)

1. 그리디의 유형이 어떤 방식으로 나오는지는 이제 좀 알것 같다. 하지만 DFS, DP 등과 같이 확실하게 컨셉이 잡힌 문제와 달리 그리디는 방식만 차용할 뿐 결국 이를 풀어낼 풀이과정이 필요한데 그게 참 어렵다. 그리고 그게 정말 최적인지, 영향을 미치는 다른 요인은 없는지 고민하는 부분이 가장 어려운 일인거 같다!