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

programmers.co.kr/learn/courses/30/lessons/42883

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

 

처음에는 최대 길이가 백만이어서 O(n^2) 을 피하기 위해

투 포인터를 쓰면서 k 만큼 구간을 잘라서 벡터에 넣은뒤, 최대 값을 구하려고 했으나,

코드가 난잡해지고, 오류가 많이 났다.

그래서 다른 사람의 코드를 보고 훨씬 더 간단한 방법을 보게 되었다

부분 구간을 잘라서 넣는게 아니라,

그냥 처음 부터 가장 큰 값을 찾아내서, 거기서부터 시작하여 k 개를 만들어 내면 되었다.

(백준이나 코포 같은 다른 사이트의 문제도 그렇고 문제에서 제시하는 있는 그대로 구현하기 보다는

최대한 단순하게 생각해보는게 첫번째로 중요한듯 하다.)

 

- c++

 

#include <bits/stdc++.h>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
 
    int len = number.length() - k;
    int start = 0;
 
    for (int i = 0; i < len; ++i) {
        char max_num = number[start];
        int max_idx = start;
        for (int j = start; j <= k + i; ++j) {
            if (max_num < number[j]) {
                max_num = number[j];
                max_idx = j;
            }
        }
        start = max_idx + 1;
        answer += max_num;
    }
    return answer;
}

 

 

 

 

 

- 참조

mtoc.tistory.com/80

프로그래머스 Level 2 큰 수 만들기(Greedy) C++