[프로그래머스] 조이스틱

jh Seo·2023년 8월 24일
DFS백트래킹프로그래머스한번에 푼 문제
1

프로그래머스

목록 보기
27/33
post-custom-banner

개요

프로그래머스 : 조이스틱

  • 문제 설명
    조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
    ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

    조이스틱을 각 방향으로 움직이면 아래와 같습니다.

    ▲ - 다음 알파벳
    ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
    ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
    ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)
    예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

  • 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
  • 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
  • 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
    따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
    만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

접근 방식

  1. 처음에는 좀 고민을 많이 했다.
    알파벳 순서가 제일 적은걸 먼저 가야하나?
    첫번째 문자에서 제일 가까운 문자부터 가야하나?
    이런식으로 고민을 하다가 어차피 중간에 A가 껴있어서 애매하므로
    모든 상황을 백트래킹 방식으로 체크를 하기로 했다.

  2. FindLocationWithLittleMove함수를 구현했다.
    DFS방식으로 모든 순서를 방문하며 움직인 숫자를 구하고
    leastMove 변수에 제일 적은 수를 기록한다.

    // prevCharIndex의 원소 다음 curCharIndex원소를 들림
void FindLocationWithLittleMove(string& origin,string& withoutA,string cur ,int prevCharIndex ,int curCharIndex, int curMoveCnt){
   if(origin[curCharIndex]=='A') return;
   
   int Move=21;
   //origin에서 prevChar에서 curChar으로 쭉 이동했을 때 거리
   Move= min(Move,abs(curCharIndex-prevCharIndex));
   //origin에서 마지막 문자로 향해서 돌아갈때의 거리
   if(prevCharIndex<curCharIndex){
       Move=min(Move,abs(prevCharIndex + (int)origin.length()-curCharIndex));
   }
   else if(curCharIndex<prevCharIndex){
       Move= min(Move,abs(curCharIndex + (int)origin.length()-prevCharIndex)); 
   }
   else 
       Move=0;
   Move+=AtoTarget(origin[curCharIndex]);
   visited[curCharIndex]=true;    
   curMoveCnt+=Move;
   cur+=origin[curCharIndex];
   //가지치기
   if(leastMove<curMoveCnt) return;
   if(cur.size()==withoutA.size()){
       leastMove=curMoveCnt;
       return;
   }
   for(int i=1;i<origin.length();i++){
       if(visited[i]) continue;
       FindLocationWithLittleMove(origin,withoutA,cur,curCharIndex,i,curMoveCnt);
       visited[i]=false;
   }
   
}

  3. 함수 내부를 봐보자.

    // prevCharIndex의 원소 다음 curCharIndex원소를 들림
void FindLocationWithLittleMove(string& origin,
string& withoutA,
string cur ,
int prevCharIndex ,
int curCharIndex, 
int curMoveCnt){

    인자로는 순서대로
    맨 처음 인자로 들어온 string변수,
    A를 제거한 string변수,
    이전 재귀단계에서 처리한 char형 변수 배열,
    이전 재귀단계에서 char형 변수가 origin에서 몇번째 인덱스인지,
    현재 재귀단계에서 처리할 char형 변수가 origin에서 몇번째 인덱스인지,
    이전 재귀단계까지 조이스틱을 얼마나 움직였는지이다.

     if(origin[curCharIndex]=='A') return;

    현재 처리해야하는 char형 변수가 A면 리턴한다.
    A는 조이스틱을 돌리지 않는 아이라 신경쓸 필요가 없다.

    int Move=21;
  //origin에서 prevChar에서 curChar으로 쭉 이동했을 때 거리
  Move= min(Move,abs(curCharIndex-prevCharIndex));
  //origin에서 마지막 문자로 향해서 돌아갈때의 거리
  if(prevCharIndex<curCharIndex){
      Move=min(Move,abs(prevCharIndex + (int)origin.length()-curCharIndex));
  }
  else if(curCharIndex<prevCharIndex){
      Move= min(Move,abs(curCharIndex + (int)origin.length()-prevCharIndex)); 
  }
  else 
      Move=0;
  Move+=AtoTarget(origin[curCharIndex]);

    Move는 (prevCharIndex인덱스에서 curCharIndex인덱스까지 조이스틱을 움직인 횟수+ curCharIndex에서 해당 알파벳에 맞게 조이스틱을 움직인 횟수)의 최솟값이다.

    일단 origin 변수에서 prevCharIndex 인덱스에서 curCharIndex인덱스까지
    가는 거리의 최소값을 구하자.

  • curCharIndex- prevCharIndex는 직선거리를 구한 식이다.

  • abs(prevCharIndex + (int)origin.length()-curCharIndex)는 prevCharIndex가 curCharIndex보다 앞 인덱스일때, 직선거리가 아닌, 0번째 인덱스를 통과해 돌아가는 거리다.

  • abs(curCharIndex + (int)origin.length()-prevCharIndex)는
    그 반대일 때 0번째 인덱스를 통과해 돌아가는 거리다.

    이 세 값의 최솟값을 Move에 넣어준다.

    이제 curCHarIndex에서 AtoTarget함수를 이용해 해당 알파벳에 맞게 조이스틱을 움직인 횟수를 구해야한다.

    이제 Move+=AtoTarget(origin[curCharIndex]); 연산까지 해서
    Move에는 prev인덱스부터 cur인덱스까지 저장이 되어있다.

    현재 단계에 방문 했다는 뜻으로 방문 배열에 true처리를 해준다.

    visited[curCharIndex]=true;

    지금 까지 총 움직인 수에 Move값을 더 해주고,
    현재 char형 변수까지 처리했으므로, string변수 cur에 현재 char형 변수 를 추가해준다.

    curMoveCnt+=Move;
cur+=origin[curCharIndex];

    만약 현재 char형 변수까지 횟수를 처리했을 때,
    최소값을 저장하는 leastMove변수보다 크기가 크다면 가지치기를 해준다.

     //가지치기
   if(leastMove<curMoveCnt) return;

    만약 char형변수까지 처리를 했을 때, A가 없는 string형 변수 withoutA와
    사이즈가 같다면 모든 A를 빼고 나머지 알파벳을 다 처리한 경우이다.
    leastMove변수에 현재 움직인 횟수를 저장해준다. 

     if(cur.size()==withoutA.size()){
     leastMove=curMoveCnt;
     return;
 }

    위 조건문에서 안 걸렸다면 나머지 알파벳들을 찾으러 가야한다.
    origin의 원소들을 순회하면서 방문을 안 했다면, 재귀 호출한다.
    빠져나왔다면, 해당 방문 여부를 false해줘야한다.
    트리 DFS가 아니기 때문에 방문한 알파벳을 또 방문해주는 경우가 있기 때문이다.

     for(int i=1;i<origin.length();i++){
     if(visited[i]) continue;
     FindLocationWithLittleMove(origin,withoutA,cur,curCharIndex,i,curMoveCnt);
     visited[i]=false;
 }
  1. AtoTarget함수
    int AtoTarget(char target){
   int cnt=target-'A';
  
   if(cnt>=13){
     return 26-cnt;  
   } 
   else{ 
   return cnt;
   }
}
    target값에 'A'를 빼서 숫자를 구하고 ,
    알파벳 숫자의 절반인 13을 안 넘으면 해당 cnt값을 리턴
    13을 넘으면 A에서 Z로 먼저 간다음 해당 알파벳을 찾아야하므로
    26-cnt값을 리턴하면 된다.

전체코드

#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iostream>
int leastMove=2'100'000'000;
bool visited[21];
using namespace std;

int AtoTarget(char target){
    int cnt=target-'A';
   
    if(cnt>=13){
      return 26-cnt;  
    } 
    else{ 
    return cnt;
    }
}
// prevCharIndex의 원소 다음 curCharIndex원소를 들림
void FindLocationWithLittleMove(string& origin,string& withoutA,string cur ,int prevCharIndex ,int curCharIndex, int curMoveCnt){
    if(origin[curCharIndex]=='A') return;
    
    int Move=21;
    //origin에서 prevChar에서 curChar으로 쭉 이동했을 때 거리
    Move= min(Move,abs(curCharIndex-prevCharIndex));
    //origin에서 마지막 문자로 향해서 돌아갈때의 거리
    if(prevCharIndex<curCharIndex){
        Move=min(Move,abs(prevCharIndex + (int)origin.length()-curCharIndex));
    }
    else if(curCharIndex<prevCharIndex){
        Move= min(Move,abs(curCharIndex + (int)origin.length()-prevCharIndex)); 
    }
    else 
        Move=0;
    Move+=AtoTarget(origin[curCharIndex]);
    visited[curCharIndex]=true;    
    curMoveCnt+=Move;
    cur+=origin[curCharIndex];
    //가지치기
    if(leastMove<curMoveCnt) return;
    if(cur.size()==withoutA.size()){
        leastMove=curMoveCnt;
        return;
    }
    for(int i=1;i<origin.length();i++){
        if(visited[i]) continue;
        FindLocationWithLittleMove(origin,withoutA,cur,curCharIndex,i,curMoveCnt);
        visited[i]=false;
    }
    
}

int solution(string name) {
    int answer = 0;
    string withoutA="";
    for(char elem : name){
        if(elem!='A')
        withoutA+=elem;
    }
    string start="";
    if(name[0]!='A')
     start+=name[0];
    //여기에 visited[i]=false를 안해주면 첫번째 방문한곳은 false되는 부분이 findloc함수내부에 없다
    for(int i=1;i<name.length();i++){
        visited[i]=true;   
        FindLocationWithLittleMove(name,withoutA,start,0,i,AtoTarget(name[0]));
        visited[i]=false;
    }
    //초기값이 나오면 첫글자만 있는 상태
    if(leastMove==2100000000) return name[0]-'A';
    return answer=leastMove;
}

문풀후생

  1. 막혔던 부분이 여러 개 있었다.

  • FindLocation~ 함수가 현재 처리해야할 char형 변수가 'A'라면
    바로 걸러버려서 AAA 이런 값이면 leastMove의 초기값인 21억을 뱉어낸다.
    그리고 함수 자체가 이전char형 변수~ 현재 char형 변수를 조사하기 때문에
    첫 문자는 조사하지 않는다.
    그래서 함수 실행 후, 21억이라면 첫 글자만 남아있는 상태이다.
    따라서, return name[0]-'A'를 해준다.

  • 위 내용과 연결되는 부분으로 함수가 이전 문자는 조사하지 않는 특성 때문에,
    Solution함수에서 처음으로 FindLoc~함수 호출할 때, 방문 배열 처리를 주의해야한다. 

       //여기에 visited[i]=false를 안해주면 첫번째 방문한곳은 false되는 부분이 findloc함수내부에 없다
   for(int i=1;i<name.length();i++){
       FindLocationWithLittleMove(name,withoutA,start,0,i,AtoTarget(name[0]));
   }

    처음에 이런식으로 방문 배열 처리 함수내부에서 해주겠지 하고 돌렸다가, 답이 제대로 안 나왔다.
    Solution함수에서 맨 처음 함수 호출하게 되면 이전 index 0번, cur 인덱스 i번인 함수를 호출한다.
    처음 방문하게 되는 i번은 함수내부에서 방문 처리되지만
    이전 노드는 처리를 하지 않는 함수 구조상 방문이 끝났을때 i번을 false처리해주는 부분이 없다.

    따라서 Solution함수에서도 visited[i]=false 처리를 해줘야한다.

profile
jh Seo
코딩 창고!
이전 포스트

[프로그래머스] 체육복

다음 포스트

[프로그래머스] 큰 수 만들기

post-custom-banner

0개의 댓글