프로그래머스 - 조이스틱

---

 

조이스틱 상, 하, 좌, 우 배열을 만들고

 

배열의 처음부터 좌, 우로 for문을 통해 하나씩 증가시키면서 수정해야하는 가장 가까운 문자열을 찾고

그 문자열을 아스키값으로 비교해서 위, 아래 중 가까운 쪽으로 조이스틱 배열을 더해줍니다

 

이것을 계속 반복

 

저번에 풀다 포기하고 처음부터 다시 풀어서 해결하긴 했는데

이렇게 하니 시간이 아슬아슬하게 통과되는 느낌 조금만 더 복잡했어도 타임아웃으로 실패했을 것 같다.

 

그리디 문제이다 보니 답이 최적화 되지는 않은 것 같다.

 

이유는 특정 인덱스에서 좌, 우 로 동일한 거리만큼 수정해야 하는 문자가 있다면 무조건 오른쪽부터 검사해서 수정해도 정답으로 나오는 것 같다.

 

개인적으로 알고리즘 공부가 아직 깊진 않지만 그리디 알고리즘이 제일 이해가 안되는 것 같다

 

func solution(_ name: String) -> Int {
	//조이스틱의 상, 하, 좌, 우 카운트를 담을 배열
    var stick: [Int] = [0, 0, 0, 0]
    
    //배열을 A로 초기화 후 입력받은 값과 얼마나 차이나는지를 비교하는 배열
    let n = Array(repeating: "A", count: name.count)
    
    //해당 텍스트를 수정했는지 담는 배열
    var visited = Array(repeating: false, count: name.count)
    
    let string = name.map { $0 }
    
    //먼저 입력받은 숫자에서 "A"은 방문했다고 변경함
    for i in 0 ... string.count - 1 {
        if string[i] == "A" {
            visited[i] = true
        }
    }
    
    //몇번째 인덱스 값을 비교중인지 담는 변수
    var count = 0

	//모든 텍스트를 방문하면 반복문 종료
    while visited.contains(false)  {
        for i in 0 ... name.count - 1 {
        
        	//오른쪽으로 i만큼 이동해서 문자열이 다르면 조이스틱[2]를 증가시킴
            if visited[(count + i) % string.count] == false {
                count = (count + i) % string.count
                stick[2] += i
                visited[count] = true
                break
                
                //왼쪽으로 i만큼 이동해서 문자열이 다르면 조이스틱[3]을 증가
            } else if visited[(count - i + string.count) % string.count] == false {
                count = (count - i + string.count) % string.count
                stick[3] += i
                
                visited[count] = true
                
                break
            }
            
        }
        
        //문자열을 비교해서 위, 아래 중 가까운 쪽을 계산해서 조이스틱[0], 조이스틱[1]에 담아줌
        if Int(string[count].asciiValue!) - Int(UnicodeScalar(n[count])!.value) < 26 - (Int(string[count].asciiValue!) - 65) {
            stick[0] += Int(string[count].asciiValue!) - Int(UnicodeScalar(n[count])!.value)
        } else {
            stick[0] += 26 - (Int(string[count].asciiValue!) - 65)
        }
    }
    
    return stick.reduce(0, { $0 + $1 })
}