99클럽 코테 스터디 20일차 큰 수 만들기

📝 문제

프로그래머스

🔥 시도해본 접근 방식

우선 이 문제는 어떻게 가장 큰 수를 만들 수 있는지 방법을 먼저 생각해야 했다.

나는 주어진 숫자의 앞쪽부터 두개씩 비교하여

앞에있는 수가 뒤에있는 수 보다 작으면 제거하고,

크다면 다음 두 개를 비교하는 식으로 접근하였다.

 

1️⃣ 첫번째 시도

import java.util.LinkedList;

class Solution {
    public String solution(String number, int k) {
        LinkedList<Integer> numbers = new LinkedList<>();

        for (String num : number.split("")) {
            numbers.add(Integer.parseInt(num));
        }

        int i = 0;
        while (k > 0) {
            if (numbers.get(i) < numbers.get(i + 1)) {
                numbers.remove(i);
                k--;
                i = 0;
            } else if (i < numbers.size() - 1) {
                i++;
            }
        }

        StringBuilder answer = new StringBuilder();
        for (Integer num : numbers) {
            answer.append(num);
        }

        return answer.toString();
    }
}

다음과 같이 코드를 제출하였고 시간초과, 런타임 에러로 인해 첫번째 시도는 실패하였다.

무엇이 문제였을지 곰곰히 생각해보았고 떠오른것은

만약, 숫자가 점점 작아지는 숫자면 (ex. 333332222111) IndexOutOfBoundsException이 발생하는 경우를 찾았다.

 

2️⃣ 두번째 시도

import java.util.LinkedList;

class Solution {
    public String solution(String number, int k) {
        LinkedList<Integer> numbers = new LinkedList<>();

        for (String num : number.split("")) {
            numbers.add(Integer.parseInt(num));
        }

        int i = 0;

        // number에서 숫자가 k개 만큼 제거될 때 까지 반복
        while (k > 0) {
            if (i >= numbers.size() - 1) { // numbers의 마지막 인덱스까지 지울 숫자가 없으면 마지막 인덱스를 지우고 i를 초기화
                numbers.remove(numbers.size() - 1);
                k--;
                i = 0;
            } else if (numbers.get(i) < numbers.get(i + 1)) { // i+1 번째 숫자가 i번째 숫자 보다 크면 i번째 숫자 제거
                numbers.remove(i);
                k--;
                i = 0;
            } else {
                i++;
            }
        }

        StringBuilder answer = new StringBuilder();
        for (Integer num : numbers) {
            answer.append(num);
        }

        return answer.toString();
    }
}

탐색 인덱스가 초과할 수 있는 결함을 고쳐서 다시 제출해보았으나 여전히 테스트 케이스 7,8,10 에서 시간초과가 뜨고 있었다.

현재 코드를 보았을 때 숫자를 제거한 뒤 탐색 시작 위치를 무조건 맨 처음(0)인덱스로 초기화 하는데

이것을 이미 검증된 숫자 이 후 부터 하도록 수정해보았다.

3️⃣ 세번째 시도

import java.util.LinkedList;

class Solution {
    public String solution(String number, int k) {
        LinkedList<Integer> numbers = new LinkedList<>();

        for (String num : number.split("")) {
            numbers.add(Integer.parseInt(num));
        }

        int i = 0;

        // number에서 숫자가 k개 만큼 제거될 때 까지 반복
        while (k > 0) {
            if (i >= numbers.size() - 1) { // numbers의 마지막 인덱스까지 지울 숫자가 없으면 마지막 인덱스 숫자를 제거
                numbers.remove(numbers.size() - 1);
                k--;
            } else if (numbers.get(i) < numbers.get(i + 1)) { // i+1 번째 숫자가 i번째 숫자 보다 크면 i번째 숫자 제거
                numbers.remove(i);
                k--;
                
                // 숫자를 제거한 후 탐색 시작 위치를 이미 검증된 숫자들 이후부터 하도록 i 값 초기화
                i = i > 0 ? i - 1 : 0;
            } else {
                i++;
            }
        }
        
        StringBuilder answer = new StringBuilder();
        for (Integer num : numbers) {
            answer.append(num);
        }

        return answer.toString();
    }
}

위와 같이 수정하였고 테스트 케이스 7, 8 번은 통과 되었으나 10번은 여전히 시간초과가 발생하였다.

코드에서 리스트를 생성하는 반복문과 answer를 만드는 반복문을 제거하면 시간적인 측면에서 개선이 있을까 하여 수정해보았다.

 

4️⃣ 네번째 시도

class Solution {
    public String solution(String number, int k) {
        int i = 0;

        // number에서 숫자가 k개 만큼 제거될 때 까지 반복
        while (k > 0) {
            if (i >= number.length() - 1) { // numbers의 마지막 인덱스까지 지울 숫자가 없으면 마지막 인덱스 숫자를 제거
                number = number.substring(0, number.length() - 1);
                k--;
            } else if (number.charAt(i) < number.charAt(i + 1)) { // i+1 번째 숫자가 i번째 숫자 보다 크면 i번째 숫자 제거
                number = number.substring(0, i) + number.substring(i + 1);
                k--;

                // 숫자를 제거한 후 탐색 시작 위치를 이미 검증된 숫자들 이후부터 하도록 i 값 초기화
                i = i > 0 ? i - 1 : 0;
            } else {
                i++;
            }
        }

        return number;
    }
}

뭐가 문제인지 도저히 모르겠어서 질문게시판을 보았더니 StringBuilder를 사용하라는 조언이 있어서 수정해보았다.

 

✨ 성공 코드

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

        // number에서 숫자가 k개 만큼 제거될 때 까지 반복
        while (k > 0) {
            if (i >= sb_number.length() - 1) { // numbers의 마지막 인덱스까지 지울 숫자가 없으면 마지막 인덱스 숫자를 제거
                sb_number.deleteCharAt(sb_number.length() - 1);
                k--;
            } else if (sb_number.charAt(i) < sb_number.charAt(i + 1)) { // i+1 번째 숫자가 i번째 숫자 보다 크면 i번째 숫자 제거
                sb_number.deleteCharAt(i);
                k--;

                // 숫자를 제거한 후 탐색 시작 위치를 이미 검증된 숫자들 이후부터 하도록 i 값 초기화
                i = i > 0 ? i - 1 : 0;
            } else {
                i++;
            }
        }

        return sb_number.toString();
    }
}

위와 같이 문자열 연산을 StringBuilder로 전면 수정하였더니 비로소 통과할 수 있었다.

이제부터는 문자열을 편집할 때 무조건 StringBuilder만 사용할 것 같다.