C++를 사용하여 주어진 숫자의 기울기(Slope) 구하기

문제 개요

이 문제에서는 하나의 숫자 N이 주어지며, 우리의 과제는 주어진 숫자의 기울기(slope)를 찾는 것입니다.

숫자의 기울기(slope)란 해당 숫자를 구성하는 자릿수 중 극댓값(maxima) 자릿수와 극솟값(minima) 자릿수의 총 개수를 의미합니다.

극댓값 자릿수(maxima digit)는 바로 앞과 뒤에 있는 이웃 자릿수보다 모두 큰 자릿수를 말합니다.

극솟값 자릿수(minima digit)는 바로 앞과 뒤에 있는 이웃 자릿수보다 모두 작은 자릿수를 말합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력

N = 9594459

출력

2

위 예시에서 '5'는 양옆의 '9'보다 작은 극솟값 자릿수이고, 가운데 '9'는 양옆의 '5'와 '4'보다 큰 극댓값 자릿수이므로 기울기는 2가 됩니다.

해결 접근 방법

이 문제의 간단한 해결 방법은 첫 번째 자릿수와 마지막 자릿수를 제외한 나머지 자릿수를 하나씩 순회하는 것입니다. 첫 자릿수와 마지막 자릿수는 이웃 자릿수가 두 개가 아니므로 극댓값이나 극솟값이 될 수 없습니다. 각 자릿수에 대해 앞뒤 자릿수와 비교하여 더 큰지 작은지를 확인하고, 최종적으로 극댓값과 극솟값의 총 개수를 반환하면 됩니다.

이 방법의 시간 복잡도는 숫자의 길이에 비례하는 O(N)으로 매우 효율적입니다.

예제

다음은 이 솔루션의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int findNumberSlope(string N, int len){
    int slope = 0;
    for (int i = 1; i < len - 1; i++) {
        if (N[i] > N[i - 1] && N[i] > N[i + 1])
            slope++;
        else if (N[i] < N[i - 1] && N[i] < N[i + 1])
            slope++;
    }
    return slope;
}
int main(){
    string N = "574473434329";
    int len = N.size();
    cout<<" The slope of the given number is "<<findNumberSlope(N, len);
    return 0;
}

출력

The slope of the given number is 7

마무리

이처럼 숫자를 문자열로 처리한 뒤 인접한 자릿수끼리 비교하는 간단한 순회만으로 숫자의 기울기를 쉽게 구할 수 있습니다. 문자열의 각 자릿수는 문자 코드로 비교되며, '0'~'9'는 코드 값이 순차적이므로 별도의 변환 없이도 크기 비교가 정확하게 이루어집니다.