[C++] 문제해결기법 과제 4: 가장 큰 수

 

길이가 N인 숫자로 된 문자열이 있다. 이 문자열에서 연속한 K개의 숫자로 만들 수 있는 가장 큰 수를 찾는 프로그램을 작성하시오. 예를 들어, 문자열이 "1414213"이고 K=3이라면, 만들 수 있는 수는 141, 414, 142, 421, 213이며 421이 이 중 가장 큰 수이다. .c/.cpp/.java 파일 하나를 제출하시오. 

 

입력 

표준 입력으로 입력을 받는다. 첫줄에 두 정수 N과 K가 주어지는데, N은 문자열의 길이로 1 이상 100,000 이하이며, K는 문제에서 설명한 것과 같은 의미로 1 이상 10 이하이다. K가 N보다 큰 경우는 없다. 다음 줄에는 길이가 N인 숫자로 이루어진 문자열이 주어진다. 

 

출력 

표준 출력으로 출력한다. 한 줄에 정수 하나를 출력하는데, 이 수는 문제의 조건을 만족하는 수이다. 답이 0으로 시작한다면 0을 모두 제거한다. 예를 들어, 답이 0054라면 54를 출력한다. 

 

예제 입력 1

7 3

1414213

예제 출력 1

421

예제 입력 2

8 3

00000013

예제 출력 2

13

 

#include <iostream>
#include <string>
using namespace std;
 
// K가 10인 경우를 위해 long long 선언
long long max(long long a, long long b)
{
    return (a > b) ? a : b;
}
 
long long LargestNum(string S, int N, int K)
{
    int pos = 0;
    if (N <= 4094) pos = N - K + 1;  // 만들 수 있는 수 N-K+1개
    else pos = S.length() - K + 1;  // abort 오류 때문
    long long* parsedS = new long long[pos];
    for (int i = 0; i < pos; i++) { parsedS[i] = stoll(S.substr(i, K)); }
 
    long long result = parsedS[0];
    for (int j = 1; j < pos; j++) { result = max(parsedS[j], result); }
 
    return result;
}
 
// N은 1 이상 100,000 이하, K는 1 이상 10 이하, K가 N보다 큰 경우는 없다.
int main()
{
    int N, K;
    string S;
    cin >> N >> K;
    cin.ignore();
    getline(cin, S);
    cout << LargestNum(S, N, K);
    return 0;
}

 

점수 10/10