프로그래머스 / 마법의 엘리베이터 / C++

일반적인 BFS풀이로 구하기엔 입력의 숫자가 1억으로 너무 큽니다.

문제의 의도가 BFS가 아닌게 느껴지고, 최소의 횟수를 찾는 경우기 때문에 그리디 알고리즘 풀이의 방식일거라

생각했습니다. 

 

실제 풀이 역시 일의자리 숫자부터 5를 기준으로 큰지 작은지 판별합니다. 만약 5인 경우에는 올림을 했을때, 그 다음

자리의 숫자에 영향을 미치기 때문에 그 다음자리의 숫자를 0~4 , 5~9에 따라 버리거나 올리거나를 결정해야 합니다.

그 다음 숫자가 5라면 올려서 6을 만드는게 최소인 경우이고, 4일때는 굳이 올려서 5를 만들필요 없이 버리면 됩니다.

 

마지막으로 코드 안에서 가장 큰 자리의 숫자(맨 앞자리 숫자)의 경우에는 연산이 다른 자리의 숫자들과 조금 다르기

때문에 그 부분만은 따로 case분류하여 코드를 구현하시면 모든 테스트케이스에 정답을 받으실 수 있습니다.

 

 

 

#include <string>
#include <vector>
 
using namespace std;
 
//일반적인 BFS와는 다른느낌. Greedy일 확률이 높음. 규칙을 찾아야함.
 
int solution(int storey) {
    int answer = 0;
    
    string s = to_string(storey);
    int tmp = s.length() - 1;
    
    while(tmp >= 0)
    {
        int cur = s[tmp] - '0';
        
        if (tmp == 0)
        {
            if (cur > 5)
            {
                answer += 10-cur+1;
                break;
            }
            else
            {
                answer += cur-0;
                break;
            }
        }
        
        if (cur > 5)
        {
            answer += 10 - cur;
            s[tmp-1] = (char)(s[tmp-1] -'0'+1+48);
            tmp--;
        }
        if (cur < 5)
        {
            answer += cur - 0;
            tmp--;
        }
        if (cur == 5)
        {
            int check = tmp-1;
            
            if (s[check]-'0' >= 5)
            {
                answer += 10 - 5;
                s[check] = (char)(s[check] -'0'+1+48);
                tmp--;
            }            
            if (s[check]-'0' < 5)
            {
                answer += cur - 0;
                tmp--;
            }
        }
    }
    
    return answer;
}