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

 

▼ 문제 링크

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

 

그 옛날 오락실 게임기에서 랭킹에 올라갈 만큼(보통 10~20등 내외) 기록을 세우면 닉네임을 입력하라는 화면이 뜬다. A부터 Z까지, 보통 3자리, 종종 4자리 닉네임을 입력할 수 있곤 했다. 조이스틱을 위로 올리면 A -> B로, 반대로 아래로 내리면 B -> A로 이동한다. 좌우로 이동해서 닉네임 자리를 옮길 수 있다.

즉, 이 문제는 이 오락실 게임기로 주어진 닉네임을 입력할 때 움직여야 할 최소 횟수를 구하는 문제다.

이 문제의 상위 분류는 '탐욕법(Greedy)'이다. 

탐욕법이란?
탐욕법이란 문제 해결의 전체가 아니라 문제 해결을 위해 나눈 각각의 작은 단계에서 가장 최선의 선택을 하는 기법

닉네임 전체를 만들기 위해 멀리 생각해 가장 최적의 수를 찾는 게 아니라 하나하나 눈 앞의 닉네임을 만들기 위한 최적의 수를 찾아 그것들을 합치면 해답이 될거란 말이다.

 

 

# 풀이 1
해당 커서 위치 좌/우 글자를 만들기 위한 조이스틱 횟수 비교

import Foundation

func solution(_ name: String) -> Int {
    
    var names = name.map{String($0)}
    var index = 0
    var count = countMoves(names[index])
    names[index] = "A"
    let result = Array(repeating: "A", count: names.count)
    
    while names != result {
        var next1 = 0
        var count1 = 0
        var interval1 = 0
        
        // 닉네임을 만들기 위해 조이스틱을 조작해야 하는 횟수 (오른쪽 글자로 이동)
        repeat {
            interval1 += 1
            next1 = index + interval1 >= names.count ? index + interval1 - names.count : index + interval1
            count1 = countMoves(names[next1])
        } while count1 == 0
        
        var next2 = 0
        var count2 = 0
        var interval2 = 0
        
        // 닉네임을 만들기 위해 조이스틱을 조작해야 하는 횟수 (왼쪽 글자로 이동)
        repeat {
            interval2 += 1
            next2 = index - interval2 < 0 ? names.count - 1 : index - interval2
            count2 = countMoves(names[next2])
        } while count2 == 0
        
        // 조작 횟수가 더 적은 쪽 선택
        if interval1 < interval2 {
            index = next1
            count = count + count1 + interval1
        } else {
            index = next2
            count = count + count2 + interval2
        }
        
        names[index] = "A"
    }
    
    return count
}

// 주어진 글자를 만들기 위해 조이스틱을 조작해야 하는 횟수를 구하는 함수
func countMoves(_ word: String) -> Int {
    
    if word == "A" {
        return 0
    }
    
    // 조이스틱을 위로 조작할 때 (인덱스 0을 사용하지 않기 위해 띄어쓰기 포함)
    let alphabets1 = " BCDEFGHIJKLMN".map{String($0)}
    // 조이스틱을 아래로 조작할 때 (역순) (인덱스 0을 사용하지 않기 위해 띄어쓰기 포함)
    let alphabets2 = " ZYXWVUTSRQPO".map{String($0)}
    var index = 0
    
    if alphabets1.contains(word) {
        while word != alphabets1[index] {
            index += 1
        }
    } else if alphabets2.contains(word) {
        while word != alphabets2[index] {
            index += 1
        }
    }
    
    return index
}

주어진 테스트 케이스는 모두 성공했으나, 제출했을 때 테스트3번이 시간 초과, 테스트11번이 실패가 떴다.

 

 

# 풀이 2
풀이 1 변형

import Foundation

func solution(_ name: String) -> Int {
    
    var names = name.map{String($0)}
    var index = 0
    var count = countMoves(names[index])
    names[index] = "A"
    let result = Array(repeating: "A", count: names.count)
    
    while names != result {
        var next1 = 0
        var count1 = 0
        var interval1 = 0
        
        var next2 = 0
        var count2 = 0
        var interval2 = 0
        
        repeat {
            interval1 += 1
            next1 = index + interval1 >= names.count ? index + interval1 - names.count : index + interval1
            count1 = countMoves(names[next1])
            
            interval2 += 1
            next2 = index - interval2 < 0 ? names.count - 1 : index - interval2
            count2 = countMoves(names[next2])
            
            if count1 != 0 || count2 != 0 {
                // count1 == 0, count2 != 0인 경우
                if count1 == 0 {
                    index = next2
                    count = count + count2 + interval2
                    break
                }
                
                // count1 != 0, count2 == 0인 경우
                if count2 == 0 {
                    index = next1
                    count = count + count1 + interval1
                    break
                }
                
                // count1 != 0, count2 != 0인 경우
                if interval1 <= interval2 {
                    index = next1
                    count = count + count1 + interval1
                    break
                } else {
                    index = next2
                    count = count + count2 + interval2
                    break
                }
            }
        } while true
        
        names[index] = "A"
    }
    
    return count
}

// 주어진 단어를 만들기 위해 조이스틱을 조작해야 하는 횟수 구하기 (위와 동일)
func countMoves(_ word: String) -> Int {
    
    if word == "A" {
        return 0
    }
    
    let alphabets1 = " BCDEFGHIJKLMN".map{String($0)}
    let alphabets2 = " ZYXWVUTSRQPO".map{String($0)}
    var index = 0
    
    if alphabets1.contains(word) {
        while word != alphabets1[index] {
            index += 1
        }
    } else if alphabets2.contains(word) {
        while word != alphabets2[index] {
            index += 1
        }
    }
    
    return index
}

[풀이 1]과 크게 다르지 않지만, 풀이 2에서 중요한 다른 점이 있다면, [풀이 2]는 중간에 끝낸다는 점

[풀이 1]에서는 repeat-while문을 각각 따로 돌려 원하는 단어를 완성할 때까지 반복해서 마지막에 조작 횟수를 구하는 반면

[풀이 2]에서는 repeat-while문 안에 왼쪽/오른쪽 단어를 만들기 위한 조작 횟수를 한꺼번에 구하는데, 한꺼번에 구하게 되면 어느 한쪽의 단어가 먼저 완성되면 다른쪽 단어를 만들기 위한 횟수는 구하지 않아도 된다. 어차피 앞의 것보다 더 많은 횟수가 필요할테니까 필요 없다.

불필요한 반복 횟수를 줄임으로써 시간 초과 문제를 해결!