프로그래머스 - 큰 수 만들기 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

 

 

문제 풀이

answer의 크기는 (number의 크기) - k이다. 따라서 첫 번째 for문은 number.size() - k만큼 돈다.

그리고 다음의 과정을 거친다.

 

1.  0 ~ k에서 가장 큰 수를 찾아 해당 인덱스가 j라면 현재 인덱스(cur)를 j로 바꿔주고 answer에 넣는다.

2. 다시 cur + 1부터 k + i까지 가장 큰 수를 찾는다. 반복.

 

3번 테스트 케이스로 예를 들어보면, "4177252841"에서
0 ~ k를 탐색하면 최댓값 7이 있는 인덱스는 2이므로 cur=2, answer에는 7을 추가한다.

다시 3(cur + 1)부터 5(k + i)까지 탐색하면 최댓값은 7, 인덱스는 3이므로 cur=3, answer에는 7을 추가한다.

 

이 과정을 쭉 거치면 i=5일 때, 종료지점이고 answer에는 77584가 들어있는 상태이다.

그러면 4가 있던 인덱스는 8이므로 9(cur + 1)부터 9까지 돌며 마지막 1을 추가한다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

string solution(string number, int k) {
    string answer = "";
    int cur = 0;
    
    for(int i=0; i<number.size() - k; i++){
        char maxNum = number[cur];
        
        for(int j=cur; j<=k + i; j++){
            if(maxNum < number[j]){
                maxNum = number[j];
                cur = j;
            }
        }
        
        cur++;
        answer += maxNum;
    }
    
    
    return answer;
}