[알고리즘] 프로그래머스 큰 수 만들기 -그리디-

 

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

프로그래머스

 

 

 

접근은 빠르게 했으나 테스트 10의 시간초과 때문에 고생한 문제입니다.

 

먼저 풀이법은 다음과 같습니다. (주석에 쓸려했는데 주석 쓰고 코드 돌리면 시간초과 뜨더라고요 ㅋㅋㅋ ㅠㅠ)

1. 앞자리수는 항상 뒷자리보다 큰 수가와야 한다. 그러므로 반복문을 돌며 인덱스 0부터 한칸씩 증가하면서 n, n+1을 비교해주고 앞자리수가 작다면 n 인덱스를 제거해준다. 

2. 마지막까지 온 경우 중복숫자들이거나 정렬이 잘 되있는 경우다 그 경우 가장 마지막 숫자를 제거해준다.

3. 시간초과를 막기 위한 꼼수(?) 최상위 숫자 9가오면 프리패스해준다.

4. 위 작업들을 제거해야할 개수(completeCnt == k) 를 채울 때까지 반복해준다.

 

원본 코드에서

if(answer.charAt(i) == 9){
                    continue;
                }

가 빠졌을 때는 테스트 10에서 계속 시간초과가 떳습니다. 아마 전체 문자열 다 검색하는 완전탐색 방식이라 그런 것 같습니다. 그래서 삽질을 하다가 위에 가장 큰수 9일 떄는 continue를 하게 해서 겨우겨우 통과했습니다.

하지만 시간을 보니깐 그저 운이 좋아서 통과한 것 같습니다.

 

전체 풀이는 다음과 같습니다.

class Solution {

    private static StringBuilder answer = new StringBuilder();
    private static int completeCnt = 0;

    public String solution(String number, int k) {
        answer.append(number);
        while (completeCnt < k) {
            for (int i = 0; i < answer.length() - 1; i++) {
                if(answer.charAt(i) == 9){
                    continue;
                }
                if (answer.charAt(i) < answer.charAt(i + 1)) {
                    answer.deleteCharAt(i);
                    completeCnt++;
                    break;
                }
                if (i == answer.length() - 2) {
                    answer.deleteCharAt(i + 1);
                    completeCnt++;
                    break;
                }
            }
        }
        return answer.toString();
    }
}

 

 

결과를 보면 알겠지만 테스트 10이 진짜 간당간당하게 통과했습니다. 원래는 틀린거지만 운으로 통과했다고 생각합니다. (주석쓰면 시간초과가 나니..)

 

다른 풀이법이 생각은 났는데 너무 귀찮은 나머지 계속 현재 코드에서 꼼수만 생각했고 물론 통과는 하였지만 매우 비효율적이 였던 것 같습니다.ㅠ  때론 코드를 지우고 다른 방법으로 접근하는게 습관을 들여야겠다고 생각합니다...

 

다른 방법 생각났던거는 나중에 한번 해보도록 하겠습니다. 

 

 

댓글과 공감은 큰 힘이됩니다. 감사합니다.!

 

 

 

 

---

K번 반복문을 돌려봤습니다.  (안되는 코드인거 알고 돌려봤습니다.)

class Solution {

    private static StringBuilder answer = new StringBuilder();
    private static int completeCnt = 0;

    public String solution(String number, int k) {
        answer.append(number);
        while (completeCnt < k) {
            for (int i = 0; i <= k; i++) {
                if (answer.charAt(i) < answer.charAt(i + 1)) {
                    delete(i);
                    break;
                }
                if (i == answer.length() - 2) {
                    delete(i + 1);
                    break;
                }
            }
        }
        return answer.toString();
    }

    public void delete(int i) {
        answer.deleteCharAt(i);
        completeCnt++;
    }
}

함수를 만드는 것과 끝까지 반복문 안 돌고 k번 만큼만 돌게 했더니 다음과 같이 9000대에서 7000대로 많이(?) 줄어서 통과했습니다. 

 

 

하지만 이 풀이는 solution.solution("87654321", 3); 의 경우 해당 케이스는 통과하지 못합니다. 프로그래머스에서 다음 테스트케이스를 추가해야 할 것 같습니다.

 

 

 

 

 

---

추가로  신기한게 코틀린 코드는 처음 원본 자바코드와 같은 로직인데 또 여유롭게 통과한다.

흠...?

class Solution {
    fun solution(number: String, k: Int): String {
        val answer = StringBuilder(number)
        var completeCnt = 0
        while (completeCnt < k) {
            for (i in 0 until answer.length - 1) {
                if (answer[i].toInt() == 9) {
                    continue
                }
                if (answer[i] < answer[i + 1]) {
                    answer.deleteCharAt(i)
                    completeCnt++
                    break
                }
                if (i == answer.length - 2) {
                    answer.deleteCharAt(i + 1)
                    completeCnt++
                    break
                }
            }
        }
        return answer.toString()
    }
}