[Coding Test | Programmers] -Make a big number (Java)

큰 수 만들기

Approach

This problem was suitable for applying a greedy algorithm. I approached to solve by Removing one number at all location and picked maximum number of them, but this solution couldn't pass 1 testcase as timeout

I miss one point that solution depended on k, The calculation to get maximum number is chosing the largest number of digits first. In order to do that, we need to find a range where we can get the places we are looking for now

Algorithm & Data Structure

greedy

Time Complexity

O((n-k) * K)

Code

class Solution {
    public String solution(String number, int k) {
    StringBuilder result = new StringBuilder();
    int length = number.length();
    int startIndex = 0;
    int maxLength = length - k;

    while (result.length() < maxLength) {
        int max = -1;
        int endIndex = k + result.length();

        // search StartIndex to EndIndex
        for (int i = startIndex; i <= endIndex; i++) {
            int current = number.charAt(i) - '0';
            if (current > max) {
                max = current;
                startIndex = i + 1;
            }
        }

        result.append(max);
    }
    return result.toString();
    }

}