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

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

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

[문제 설명]

주어진 숫자에서 k개를 제거해서 가장 큰 수를 만드는 문제입니다.

[처음 생각한 접근 방법]

앞뒤를 비교해서 앞에 숫자가 뒤에 숫자보다 작으면(오름차순) 앞에 숫자를 없애기

k가 0보다 크면 반복

=> if : numbers의 i,i+1번째 문자 비교해서 i+1이 크면(오름차순) i삭제하고 i = 0, 숫자 하나 제거했으므로 k--

=> else : numbers의 i,i+1번째 문자 비교해서 i+1이 작으면(내림차순) i++

=> if : i가 numbers.length-1과 같으면 break (문자의 끝에 도달했으므로)

반복문이 끝나고

=>if : k가 0보다 크면, numbers의 마지막부터 k개 삭제(만약 쭉 내림차순이었으면, 문자가 하나도 삭제되지 않으므로 뒤에서부터 삭제)

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder(number);

        int i = 0;
        while (k > 0) {
            if (sb.charAt(i) < sb.charAt(i+1)) {
                sb.deleteCharAt(i);
                // 원래 여기 i = 0이 들어갔는데, 생각해보니 i는 0이 될 필요가 없습니다. 이전 문자열들은 이미 다 처리가 됐기 때문에.
                if (i > 0) i--;
                else i = 0;

                k--;
            } else {
                i++;
            }

            if (i == number.length()-1) break;
        }


        if (k > 0) sb.delete(sb.length()-k,sb.length());
        return sb.toString();
    }
}

풀긴 풀었는데 느리다.

프로그래머스에서 스택으로 푼 풀이를 봤는데, 확실히 다르다.

나처럼 여러번 이전부터 검색할 필요도 없고, 코드 자체도 깔끔하다.

이 문제는 다음에 한 번 다시 풀어봐야겠다.