[프로그래머스] 탐욕법(Greedy) 조이스틱 with Swift

안녕하세요. 오늘은 프로그래머스 조이스틱 문제를 풀어보겠습니다!

 

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

 

조이스틱 문제는 분류된 카테고리와 같이 탐욕알고리즘으로 문제를 해결하실 수 있습니다!

 

우선 알파벳과 알파벳간의 최소 이동거리를 구해줍니다!

 

삼항연산자를 이용해 최적값을 구해줍니다!

for i in name.utf8 {
    count = Int(i)-Int(a.asciiValue!)
    count = count > 26-count ? 26-count : count
    makeNameCount.append(count)
}

 

이후에 좌우로 이동하는 방향도 탐욕알고리즘을 이용해 삼항연산자로 이동방향을 정해줍니다!

var nextRightPoint = 0
var nextLeftPoint = 0
var rightDistance = 0
var leftDistance = 0
var isChanged = false
for i in 1..<makeNameCount.count { 
    nextRightPoint = currentPoint + i >= makeNameCount.count ? 
    	currentPoint + i - makeNameCount.count : currentPoint + i
    
    if makeNameCount[nextRightPoint] != 0 {
        isChanged = true
        rightDistance = i
        break
    }
}
for i in 1..<makeNameCount.count { 
    nextLeftPoint = currentPoint - i < 0 ? 
    	currentPoint - i + makeNameCount.count : currentPoint - i
    
    if makeNameCount[nextLeftPoint] != 0 {
        isChanged = true
        leftDistance = i
        break
    }
}
currentPoint = rightDistance <= leftDistance ? nextRightPoint : nextLeftPoint
answer = rightDistance <= leftDistance ? answer + rightDistance : answer + leftDistance

 

이렇게 위아래 좌우 모두 탐욕알고리즘을 적용하여 최적해를 구하실 수 있습니다!

 

그리고 11번 테스트 케이스가 틀리시면 좌우가 거리가같을때 우로 이동하시면 문제가 해결됩니다!

 

import Foundation

func solution(_ name:String) -> Int {
    var makeNameCount:[Int] = []
    var a:Character = "A"
    
    var count = 0
    for i in name.utf8 {
        count = Int(i)-Int(a.asciiValue!)
        count = count > 26-count ? 26-count : count
        makeNameCount.append(count)
    }
    
    var currentPoint = 0
    var answer = 0
    while true {
        print("\(currentPoint) \(makeNameCount[currentPoint])")
        answer += makeNameCount[currentPoint]
        makeNameCount[currentPoint] = 0
        
        var nextRightPoint = 0
        var nextLeftPoint = 0
        var rightDistance = 0
        var leftDistance = 0
        var isChanged = false
        for i in 1..<makeNameCount.count { 
            nextRightPoint = currentPoint + i >= makeNameCount.count ? 
            	currentPoint + i - makeNameCount.count : currentPoint + i
            
            if makeNameCount[nextRightPoint] != 0 {
                isChanged = true
                rightDistance = i
                break
            }
        }
        for i in 1..<makeNameCount.count { 
            nextLeftPoint = currentPoint - i < 0 ? 
            	currentPoint - i + makeNameCount.count : currentPoint - i
            
            if makeNameCount[nextLeftPoint] != 0 {
                isChanged = true
                leftDistance = i
                break
            }
        }
        currentPoint = rightDistance <= leftDistance ? nextRightPoint : nextLeftPoint
        answer = rightDistance <= leftDistance ? answer + rightDistance : answer + leftDistance
        if isChanged == false {
            break
        }
        
    }
    return answer
}

 

오늘은 여기까지입니다! 질문이 있으시면 댓글로 남겨주세요!

 

좋은 하루 되세요!