프로그래머스 - 조이스틱(c++, javascript)

문제 설명

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

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

 

 

예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다.

 

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

 

입출력 예

출처

※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.

 

풀이

이 문제는 아래와 같은 테스트 케이스를 넣었을 때

 

BABAAAAAAAAAB
기댓값 >> 14 가 정답으로 나온다.

 

문제에서 설명하는 바로는, 첫 문자에서 왼쪽으로 이동하여 마지막으로 갈수는 있지만, 마지막에서 오른쪽으로 이동하여 처음으로 올 수 있다고는 따로 명시돼 있지 않다. 그래서 후자는 안된다고 생각하고 풀었다.

 

사실 원래 최솟값을 구하려면 이 문제의 정답은 8이 나와야 한다.
왜냐하면

0번째 a를 b로 바꿈 : +1
3번째 a로 이동 : +2
3번째 a를 b로 바꿈 : +1
마지막 a로 이동(왼쪽으로) : +3
마지막 a를 b로 바꿈 : +1

---

총합 : 8

---

하지만 현재 정답으로는

0번째 a를 b로 바꿈 : +1
마지막 a로 이동 : +1
마지막 a를 b로 바꿈. : +1
3번째 a로 이동(왼쪽으로) : +10
3번째 a를 b로 바꿈: +1

---

총합 : 14 가 나온다.

 

그래서 위 반례를 들어 질문글을 올렸다. 나중에 확인해봐야지

프로그래머스

#include <string>
#include <vector>
using namespace std;

int solution(string name) {
    int answer = 0;
    string str;

    // A로만 구성된 초기 name을 생성한다.
    for(int i=0; i<name.size(); i++){
        str += "A";
    }

    int i=0;
    bool *visit = new bool[name.size()];
    memset(visit, false, name.size());

    while(1){
        int ascii = (int)name[i];
        visit[i] = true;

        // A와 name 과의 아스키코드 값의 차이를 구한다.
        // 이때 중앙값 N(78)을 기준으로 위로 움직일지, 아래로 움직일지 결정
        if(ascii != 65){ // 아스키코드 A : 65
            if(ascii <= 78){ // 아스키코드 N : 78 (중앙값)
                answer += ascii - 65;
            }else{
                answer += 91 - ascii; // 아스키코드 Z : 90
            }
        }

        str[i] = name[i];
        if(str == name) break;

        // 커서를 왼쪽 or 오른쪽으로 갈지 결정
        for(int j = 1; j < name.size(); j++){

            if(i+j < name.size() && name[i+j] != 'A' && !visit[i+j]){
                i += j;
                answer +=j;
                break;
            }

            if(i-j >= 0 && name[i-j] != 'A' && !visit[i-j]){
                i -= j;
                answer +=j;
                break;
            }

            if(i-j < 0 && name[ (name.size() + i) - j] != 'A' && !visit[(name.size() + i) - j]){
                i = (name.size() + i) - j;
                answer +=j;
                break;
            }
        }
    }

    return answer;
}

 

javascript

String.prototype.replaceAt=function(index, character) {
    return this.substr(0, index) + character + this.substr(index+character.length);
}

function solution(name) {
    let answer = 0;
    let str = "";
    
    for(let i=0; i<name.length; i++){
        str += 'A';
    }
    
    let i=0;
    const visit = new Array(name.length).fill(false);
    
    while(true){
        const ascii = name.charCodeAt(i);
        visit[i] = true;
        
        if(ascii != 65){
            if(ascii <= 78){
                answer += ascii - 65;
            }else{
                answer += 91 - ascii;
            }
        }
        
        str = str.replaceAt(i, name.charAt(i));
        if(str == name) break;
        
        for(let j=1; j<name.length; j++){
            if(i+j < name.length && name.charAt(i+j) != 'A' && !visit[i+j]){
                i += j;
                answer +=j;
                break;
            }

            if(i-j >= 0 && name.charAt(i-j) != 'A' && !visit[i-j]){
                i -= j;
                answer +=j;
                break;
            }

            if(i-j < 0 && name.charAt( (name.length + i) - j ) != 'A' && !visit[(name.length + i) - j]){
                i = (name.length + i) - j;
                answer +=j;
                break;
            }
        }
    }
    
    return answer;
}