Programmers - 조이스틱

---

title: Programmers - 조이스틱
date: 2022-07-10
tags:

• Algorithm
• DFS

---

https://school.programmers.co.kr/learn/courses/30/lessons/42860

문제 요약

문자열이 주어진다. A로만 이루어진 초기 문자열에서 조이스틱을 조종하여 주어진 문자열을 만들어야 한다. 조이스틱의 최소 조종 횟수를 return한다.

문제 풀이

우선 'A'를 주어진 문자로 바꿀 때, 정방향으로 바꾸는 것과 역방향으로 바꾸는 것 중 횟수가 더 적은 방법으로 count 한다.
가장 중요한 부분은 바꿀 문자를 선택하기 위하여 좌우로 움직이는 것이다.
좌, 우로 움직일 수 있으며, 'A' 문자가 주어지면 바꿀 필요가 없기에 방문하지 않아도 된다.
최적의 움직임을 확인하기 위하여, 첫 문자에서 좌,우 각각 움직이는 방법 중 최적의 방법을 확인한다.
첫 위치에서 좌,우 모두 확인하는 것은 단순히 귀찮았다.
첫 위치에서 좌,우 중 좋은 방법을 확인하는 수식을 추가적으로 구성하여야 하고, 프로그램이 너무 길어진다고 판단하였다.
어차피 문자열의 길이는 최대 20으로, 한 방향을 추가적으로 확인하여도 10k 미만의 작업이 추가된다고 판단하였다.

프로그램

#include <string>
#include <algorithm>
#include <vector>

using std :: string ;
using std :: vector ;

int answer ;

int iGetMinMove ( int iIndex , vector < bool > vMove , bool toLeft , int iCnt )
{
    int iReturn = 0 ;
    int i = iIndex ;
    int iMove = 0 ;



    if ( 0 == iCnt )
        return 0 ;


    do
    {
        if ( toLeft )
            -- i ;
        else
            ++i ;

        if ( -1 == i )
            i = vMove.size () - 1 ;
        else if ( vMove.size () == i )
            i = 0 ;

        ++ iMove ;

        if ( vMove [ i ] )
        {
            vMove [ i ] = false ;
            iReturn = iGetMinMove ( i , vMove , true , iCnt - 1 ) ;
            iReturn = std :: min ( iReturn , iGetMinMove ( i , vMove , false , iCnt - 1 ) ) ;

            return iReturn + iMove ;
        }
    } while ( i != iIndex ) ;

    return 1e4 ;
}

int solution ( string name )
{
    int iLen = name.size () ;
    const char * cpName = name.data () ;
    vector < bool > vMove ( iLen , false ) ;
    int iMove = 0 ;
    int iCnt = 0 ;



    for ( int i = 0 ; i < iLen ; ++i )
    {
        if ( 'A' != cpName [ i ] )
        {
            answer += std :: min ( cpName [ i ] - 'A' , 1 + 'Z' - cpName [ i ] ) ;
            vMove [ i ] = true ;
            ++ iCnt ;
        }
    }
    if ( vMove [ 0 ] )
    {
        vMove [ 0 ] = false ;
        -- iCnt ;
    }
    iMove = iGetMinMove ( 0 , vMove , true , iCnt ) ;
    iMove = std :: min ( iMove , iGetMinMove ( 0 , vMove , false , iCnt ) ) ;


    return answer + iMove ;
}