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

 

 

- 문제 풀이

"탐욕법"을 사용하는 문제였다.

 

 

- 코드

처음에 제출한 코드는 다음과 같다.

#include <string>
#include <vector>
#include <math.h> 
using namespace std;

int solution(string name) {
    // 필요한 변수 선언
    int answer = 0;
    int idx = 0;
    
    // 위 아래 횟수 계산
    for(int i=0; i<name.length(); i++) {
        if(name[i]-'A'<=13) 
            answer += name[i]-'A';
        else 
            answer += 'Z'-name[i]+1;
    }
    
    // 왼 오 횟수 계산
    for(int i=1; i<name.length(); i++) {
        if(name[i]!='A'){
            if( fabs(i-idx) <= fabs(name.length()-fabs(i-idx)) ) {
                answer += fabs(i-idx);
                idx = i;
            }
            else {
                answer += fabs(name.length()-fabs(i-idx));
                idx = i;                
            }
        }
    }    
    
    // 계산 값 반환
    return answer;
}

 

 

하지만 위와 같은 결과가 나왔다.

이를 해결하기 위해 한 줄만에 왼, 오 움직임 횟수를 계산할 수 있도록 만들었다.

1. while문으로 다음 문자가 'A'일 땐 건너 뛰도록 하고, 

2. min() 함수를 이용해 최소의 움직임을 구할 수 있도록 했다.

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

int solution(string name) {
    // 필요한 변수 선언
    int answer = 0;
    int len = name.length();
    int move = len - 1;
    int next;
    
    // 위 아래 횟수 계산
    for(int i=0; i<name.length(); i++) {
        if(name[i]-'A'<=13) 
            answer += name[i]-'A';
        else 
            answer += 'Z'-name[i]+1;
    }
    
    // 왼 오 횟수 계산
    for(int i = 0; i < len; i++) {
        //A면 그냥 넘기기
        next = i + 1;
        while(next < len && name[next] == 'A') 
            next++;
        //최소 움직임 계산
        move = min(move, i + (len - next) + min(i, len - next));
    }
    answer += move;
    
    // 계산 값 반환
    return answer;
}

(https://mjmjmj98.tistory.com/67 코드 참고)