C++ 문자열에서 가장 긴 숫자 찾기

이 문제에서는 문자와 알파벳으로만 구성된 문자열 str이 주어지며, 우리의 목표는 문자열에서 가장 긴 숫자를 찾는 것입니다.

문제 설명

문자열 안에는 여러 개의 숫자 덩어리(연속된 숫자 문자들)가 존재할 수 있습니다. 이때 각 숫자 덩어리의 길이를 비교하여, 그중 가장 긴 숫자를 찾아 반환해야 합니다.

예제로 문제 이해하기

입력: str = "code001tutorials34124point"

출력: 34124

설명:

문자열에 포함된 숫자들은 다음과 같습니다.

001 → 길이 3
34124 → 길이 5

두 숫자 중 길이가 더 긴 것은 34124이므로 이것이 정답이 됩니다.

해결 접근 방식

가장 간단한 해결 방법은 문자열을 처음부터 끝까지 한 번 순회하면서 각 숫자의 길이와 시작 인덱스를 기록하는 것입니다.

구체적인 동작 과정은 다음과 같습니다.

문자열을 왼쪽에서 오른쪽으로 탐색합니다.
숫자 문자를 만나면, 해당 숫자 덩어리의 시작 위치를 저장하고 연속된 숫자의 개수를 셉니다.
현재 세어진 길이가 지금까지의 최대 길이보다 크면, 시작 위치와 길이를 갱신합니다.
탐색이 끝나면 저장된 시작 위치와 길이를 이용해 substr()으로 해당 숫자를 추출하여 반환합니다.

솔루션 구현 예제

#include <iostream>
using namespace std;

string findLongestNumber(string str, int l) {

    int count = 0, max = 0, maxLenPos = -1, currPos, currLen, maxLen = 0;

    for (int i = 0; i < l; i++) {
        currPos = maxLenPos;
        currLen = maxLen;
        count = 0;
        maxLen = 0;
        if (isdigit(str[i]))
            maxLenPos = i;
        while (isdigit(str[i])) {
            count++;
            i++;
            maxLen++;
        }
        if (count > max) {
            max = count;
        }
        else {
            maxLenPos = currPos;
            maxLen = currLen;
        }
    }
    return (str.substr(maxLenPos, maxLen));
}

int main() {

    string str = "code001tutorials34124point";
    int l = str.length();
    cout<<"The longest length number in string is "<<findLongestNumber(str, l);
    return 0;
}

실행 결과

The longest length number in string is 34124

동작 원리 정리

위 코드는 isdigit() 함수를 활용해 현재 문자가 숫자인지 판별합니다. 숫자가 연속되는 동안 개수를 증가시키며, 더 이상 숫자가 아니면 지금까지의 결과와 비교합니다. 이 과정을 반복하면 자연스럽게 가장 긴 숫자 덩어리의 위치와 길이를 얻을 수 있습니다.