재귀함수로 구현하다가 갑자기 생각난 방법인데 for문으로 구현해도 될 것 같다. 함수명을 dfs라 하긴했는데.. 이게 dfs가 맞나..?!
0->1->2->3-> ••• -> n과 같이 오른쪽 한 방향으로 가는 걸 기본으로 하고 0일때 0->n->n-1-> ••• 1일때 1->0->n->n-1 과 같이 각 자리에서 왼쪽 한 방향으로만 가는걸 다시 구해줬다. 마지막 커서에서 첫번째 커서로 갈 수 없으니 계속 오른쪽 방향으로 가거나 방향을 바뀌는 횟수가 2이상이면 최솟값이 나오지 않을거라고 가정하여 풀었는데 통과 해버림 🤭
import Foundation
let alphabet: [String: Int] = ["A":1,"B":2,"C":3,"D":4,"E":5,"F":6,"G":7,"H":8,"I":9,"J":10,"K":11,"L":12,"M":13,"N":14,"O":15,"P":16,"Q":17,"R":18,"S":19,"T":20,"U":21,"V":22,"W":23,"X":24,"Y":25,"Z":26]
var result = 99999999
func dfs(_ nameArr: [String], _ resultArr: [String], _ count: Int, _ cursor : Int, _ direction : Int){
if count - 1 > result || nameArr == resultArr {
if count - 1 < result{
result = count - 1
}
return
}else{
var name: [String] = nameArr
var c = 0
if nameArr[cursor] != resultArr[cursor]{
let i = alphabet[nameArr[cursor]]!
let j = alphabet[resultArr[cursor]]!
if i < j {
if (j - i) > (26 - j + i){
c = 26 - j + i
}else{
c = j - i
}
} else{
if (i - j) > (26 - i + j){
c = 26 - i + j
}else{
c = i - j
}
}
name[cursor] = resultArr[cursor]
}
var leftCursor = cursor - 1
let rightCursor = cursor + 1
if leftCursor < 0 {
leftCursor = resultArr.count - 1
}
c += 1
if direction == 1 && rightCursor < resultArr.count{
dfs(name,resultArr,count + c, rightCursor, 1)
}
dfs(name,resultArr,count + c, leftCursor, -1)
}
}
func solution(_ name:String) -> Int {
var nameArr: [String] = []
var resultArr: [String] = []
for i in name{
resultArr.append("A")
nameArr.append(String(i))
}
dfs(nameArr,resultArr,0, 0, 1)
return result
}
이 분은 먼저 알파벳이 바뀌는 횟수를 구하고 커서 이동 횟수를 구해 최솟값을 찾으신것 같다.
import Foundation
func solution(_ name:String) -> Int {
var ans = 0
let name = name.map({$0})
for i in 0..<name.count {
if name[i] != "A" {
let up = name[i].asciiValue! - 65
let down = 91 - name[i].asciiValue!
ans += Int((up<down) ? up : down)
}
}
var minMove = name.count-1
for i in 0..<name.count {
if name[i] != "A" {
var next = i + 1
while next<name.count && name[next] == "A" {
next += 1
}
let move = 2 * i + name.count - next
minMove = min(move, minMove)
}
}
return ans + minMove
}