큰수 만들기

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

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

 

1. 첫번째 풀이(10번째 테스트 케이스에서 시간 초과)

공책으로 문제를 풀어보니 현재 문자와 다음 문자를 계속 잘라 내주면 원하는 답을 얻을 수 있었다.

    static String solution1(String number, int k)
    {
        StringBuilder builder = new StringBuilder(number);
        while (k > 0)
        {
            for (int i = 0; i < builder.length()-k; i++)
            {
                if (builder.charAt(i) < builder.charAt(i+1))
                {
                    builder.deleteCharAt(i);
                    k--;
                    break;
                }
            }
        }
        return new String(builder);
    }

당당하게 답안 제출했으나 마지막 테스트 케이스에 걸려버렸다.

스트링빌더가 아무리 최적화가 잘되어있다고 해도 배열을 50만번 복사하긴 빡센가 보다.

기존 데이터에서 값을 빼는 방식이 아니라 추가하는 방식으로 해결해야 될 것 같다.

 

2. 두 번째 풀이(정답)

잘 생각이 안나길래 구글링을 해보았고 어느 블로그에서 접근법에 대해 자세히 써놨다.

접근법을 보니 어떻게 코드를 짜야할지 감이 잡혀서 코드 부분은 안보고 짜봤다.

    static String solution2(String number, int k)
    {
        int maxPosition = 0;
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < number.length() - k; i++)
        {
            char max = 0;
            for (int j = maxPosition; j <= k + i; j++)
            {
                if (max < number.charAt(j))
                {
                    max = number.charAt(j);
                    maxPosition = j + 1;
                }
            }
            builder.append(max);
        }
        return new String(builder);
    }

 

다른 사람들은 이런 방법들을 어떻게 생각해 내는지 모르겠다.

우울하다~~~