Skip to main content Link Search Menu Expand Document (external link)

마법의 엘레베이터

문제 링크

문제 설명

  • 절대값이 10의 제곱수인 정수
    • -1, 1, -10, 10, -100, 100
  • 현재 숫자 storey에서 0으로 만들기 위한 최소 더하기 횟수 반환
  • storey가 16인 경우
    • -1 6번 -10 1번 총 7번
    • +1 4번 -10 2번 총 6번
    • 최소 6번이므로 6 반환

Input

  • int storey

Output

  • int answer

example

storeyresult
166
255416

Limitation

  • 1 ≤ storey ≤ 100,000,000

풀이 과정

  • 일단 example 분석을 해보자
    • 2554
    • 21000 + 5100 + 510 + 41

    ⇒ 2+5+5+4 = 16

  • 1의 자리 숫자가 5 이하면 -1, 6 이상이면 +1
  • 10의 자리 이상 숫자는 그냥 카운팅
  • int → string 변환해서 자리수로 카운팅할 수 있나?
    • 제한적으로 가능
    • 2554는 가능
  • 2667은 어떨까?
    • 위 방식대로 하면 2+6+7+3
    • +3을 하면 2670
    • +30을 하면 2700
    • +300을 하면 3000

    ⇒ 3+3+3+3 = 12

  • string 변환해서 reverse하고 해당 자리 숫자가 5보다 크면 10-자리수를 더하고 다음 자리수에 1을 더해준다.
    • 주어진 예제는 통과했으나 blind test에서 반 정도 실패
    • 자리수가 증가하는 케이스 놓침
      • 예로 97의 경우
      • +3을 하면 100으로 증가
      • -100 한번으로 0 계산 가능, 총 횟수 4
  • 현재 자리수가 5보다 크면 answer에 10-현재숫자를 plus
  • storey에 현재 수를 자리수에 맞춰 더해줌
    • storey를 다시 string으로 변경해서 number에 대입해줌
    • 이후 number는 새로운 storey를 기준으로 계산될 것
    • 하지만 3개 케이스 실패
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int storey) {
    int answer = 0;
    int firstAns = 0;
    string number = to_string(storey);
    reverse(number.begin(), number.end());
    //1의 자리부터 시작하도록 reverse
    for (auto num : number) {
        answer += (int)num-'0';
    }

    for (int i=0; i<number.size(); i++) {
        int tmp = (int)number[i]-'0';
        cout<<i<<" : "<<tmp<<endl;
        if (tmp == 0) continue;
        if (tmp > 5) {
            cout<<"1. answer+"<<(10-tmp)<<endl;
            firstAns += (10-tmp);
            int add = 1;
            for (int j=1; j<i+1; j++) {
                add *= 10;
            }
            storey += add*(10-tmp);
            number = to_string(storey);
            cout<<"add : "<<add*(10-tmp)<<endl;
            cout<<"new number : "<<storey<<endl;
            reverse(number.begin(), number.end());
        }
        else if (tmp == 5) {
            firstAns += (10-tmp);
            if (number[i+1] >= '5') {
                int add = 1;
                for (int j=1; j<i+1; j++) {
                    add *= 10;
                }
                storey += add*(10-tmp);
                number = to_string(storey);
                cout<<"add : "<<add*(10-tmp)<<endl;
                cout<<"new number : "<<storey<<endl;
                reverse(number.begin(), number.end());
            }
        }
        else {
            cout<<"2. answer+"<<tmp<<endl;
            firstAns += tmp;
        }
    }

    answer = answer < firstAns ? answer : firstAns;

    return answer;
}

고찰

  • 접근 방식 자체는 맞았으나 케이스 분석이 좀 더 필요했다.
  • 다른 사람 코드를 확인해보니 string으로 변환할 필요 없이 % 연산을 이용해서 1의 자리 숫자를 추출했다.
  • 그리고 10으로 나눠버려서 1의 자리 수를 버리고 storey가 0이 될 때까지 while로 반복하도록 구현했다.
  • 자리수 연산을 할 때 나머지 연산자를 활용해야하는데 바로 안떠오른다.. 기억할 것
  • 참고 블로그 https://jaimemin.tistory.com/2213