(알고리즘 스터디) 8주차 월_Greedy💪_(Programmers) 큰 수 만들기

🌟 프로그래머스 / Greedy / Level 2 / 큰 수 만들기

📃 문제

프로그래머스

🚫 제한 사항

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

👀 입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

🤔 풀이 방법

1️⃣ 방법 (1)

① 아이디어

/*
➡️ 맨 앞 n 자리를 시작으로 해서 하나씩 비교하며 늘려주기

ex) 4177252841 -> [4, 1, 7, 7, 2, 5, 2, 8, 4, 1] / k = 4
    (1) 초기 세팅 (10-4 = 6) : [4, 1, 7, 7, 2, 5]
    (2) 앞에서부터 비교
        (a) index 0 & 1 비교 : 4 > 1 -> 그대로
        (b) index 1 & 2 비교 : 1 < 7 -> 앞으로 하나 와야함
            => [4, 7, 7, 2, 5, 2]
    (3) 앞에서부터 비교
        (a) index 0 & 1 비교 : 4 < 7 -> 앞으로 하나 와야함
            => [7, 7, 2, 5, 2, 8]
    (4) 앞에서부터 비교
        (a) index 0 & 1 비교 : 7 = 7 -> 다음 비교
        (b) index 1 & 2 비교 : 7 > 2 -> 다음 비교
        (c) index 2 & 3 비교 : 2 < 5 -> 앞으로 하나 와야함
            => [7, 7, 5, 2, 8, 4]
    (5) 앞에서부터 비교
        (a) index 0 & 1 비교 : 7 = 7 -> 다음 비교
        (b) index 1 & 2 비교 : 7 > 2 -> 다음 비교
        (c) index 2 & 3 비교 : 5 > 2 -> 다음 비교
        (d) index 3 & 4 비교 : 2 < 8 -> 앞으로 하나 와야함
            => [7, 7, 5, 8, 4, 1]
*/

② 코드

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        // 배열 생성 및 초기화
        int [] numArr = new int[number.length() - k];
        for (int i=0; i<numArr.length; i++) {
            numArr[i] = i;
        }
        
        // 앞에서부터 탐색
        while (true) {
            if (numArr[numArr.length-1] ==number.length()-1) {
                break;
            }
            for (int i=0; i<numArr.length-1; i++) {
                char a = number.charAt(numArr[i]);
                char b = number.charAt(numArr[i+1]);
                
                if (a < b) {
                    for (int j=i; j<numArr.length-1; j++) {
                        numArr[j] = numArr[j+1];
                    }
                    numArr[numArr.length-1] = numArr[numArr.length-2] + 1;
                    break;
                }
            }
        }
        
        // 문자열 조합
        for (int i=0; i<numArr.length; i++) {
            answer += number.charAt(numArr[i]);
        }
        return answer;
    }
}

③ 결과

➡️ 모든 케이스에 부합한 풀이 방식은 아니였다.

2️⃣  방법 (2)

① 아이디어

➡️ 조합을 사용

② 코드

class Solution {
    public static String[] numArr;
    public static long max = 0;
    public static String[] strArr;
    public static boolean[] visited;
    public static int k;
    
    public String solution(String number, int k) {
        // 쪼개서 배열로 만들기
        numArr = number.split("");
        // 배열 생성
        strArr = new String[number.length()-k];
        visited = new boolean[number.length()];
        k = k;
        
        search(0, -1);
        
        return String.valueOf(max);
    }
    public static void search(int cnt, int last) {
        if (cnt == strArr.length) {
            String tmp = "";
            for (String s : strArr) {
                tmp += s;
            }
            if (max < Long.valueOf(tmp)) {
                max = Long.valueOf(tmp);
            }
            return;
        }
        for (int i=0; i<numArr.length; i++) {
            if (!visited[i] && last < i) {
                visited[i] = true;
                strArr[cnt] = numArr[i];
                search(cnt+1, i);
                visited[i] = false;
            }
        }
    }
}

 

③ 결과

➡️ 주어진 테스트 케이스는 모두 통과했지만 정확성 테스트에서 거의 실패하였다. 다른 케이스들을 넣어보아도 문제가 없는데 왜 안돌아가는지는 모르겠다.

3️⃣ 방법 (3)

① 아이디어

/*
➡️ 주어진 길이에서 가장 큰 수를 가지는 인덱스를 확인하면서 범위를 줄여나가 인덱스 배열을 획득한다.

ex) "4177252841" / k = 4
    (1) n-k 크기의 배열 생성 int[] idxArr = new int[number.length()-k]
    (2) index 0 부터 +k(4) = 4 까지 확인
        417725(0) vs 177252(1) vs 772528(2) vs 725284(3) vs 252841(4)
        ➡️ index 2 일 때 가장 큼 => idxArr[0] = 2
    (3) index 3 부터 +k'=k-2(2) = 5 까지 확인
        72528(3) vs 25284(4) vs 52841(5)
        ➡️ index 3 일 때 가장 큼 => idxArr[1] = 3
    (4) index 4 부터 +k''=k'-0(2) = 6 까지 확인
        2528(4) vs 5284(5) vs 2841(6)
        ➡️ index 5 일 때 가장 큼 => idxArr[2] = 5
    (5) index 6 부터 +k'''= k''-1(1) = 7 까지 확인
        284 (6) vs 841 (7)
        ➡️ index 7 일 때 가장 큼 => idxArr[3] = 7
    (6) index 8 부터 +k'''' = k'''-1(0) = 8 까지 확인
        ➡️ 나머지 다 들어가야함 => idxArr[4] = 8 / idxArr[5] = 9
*/

② 코드

class Solution {
    public String solution(String number, int k) {
        // 정답 문자열
        String answer = "";
        // 구해야할 문자열의 길이
        int len = number.length() - k; 
        
        // 시작 인덱스
        int idx = 0;
        long max = 0;
        int maxIdx = 0;
        int count = len;
        
        // 숫자들을 다 뺄 때까지 반복문 수행
        while (k != 0)  {
            // 비교하여 최고값 찾기
            for (int i=idx; i<=idx+k; i++) {
                long comp = Long.valueOf(number.substring(i,i+count));
                if (comp > max) {
                    max = comp;
                    maxIdx = i;
                }
            }
            // 정답 문자열에 추가
            answer += number.charAt(maxIdx);
            // 다음 반복문 돌 준비
            k = k-(maxIdx - idx);
            idx = maxIdx + 1;
            count--;
            max = 0;
        }
        
        // 나머지 채우기
        int gap = len - answer.length();
        
        for (int i=idx; i<idx+gap; i++) {
            answer += number.charAt(i);
        }
        
        return answer;
    }
}

③ 결과

➡️ 방법 (2) 와 상황이 비슷하다.

💻 풀이 코드