[Algorithm] Programmers_큰 수 만들기 in Java

하이초·2024년 3월 13일

algorithm programmers

Algorithm

목록 보기

87/94

💡 Programmers Level.2 큰 수 만들기:

주어진 numbers에서 K개 만큼을 뺀 가장 큰 수 찾기

🌱 코드 in Java

알고리즘: Greedy

import java.util.*;

class Solution {
    public int solution(String number, int k) {
        String answer = "";
        int i = 0, pick = 0, cnt = 0, l = k, len = number.length(), n = len - k;
        
        
        while (i < l && cnt != n) { // 더 탐색할 필요 없이 뒤 모든 수를 선택해야 하거나 이미 모든 수를 앞에서 찾은 경우
            char max = 0; // 비교용
            while (i <= l) { // 해당 자릿수에서 탐색할 수 있는 최대 범위
                char now = number.charAt(i); // 
                if (now > max) { // 갱신 가능
                    max = now;
                    pick = i; // 현재 선택 지점
                }
                i++;
            }
            answer += max; // 문자열 더하기
            cnt++; // 완성된 길이 측정
            i = pick + 1;
            l = len > l + 1 ? l + 1 : l;
        }
        if (cnt != n) // 아직 완성되지 못하고 뒤의 문자열을 다 더해야 하는 경우
            answer += number.substring(i, len);
        return answer;
    }
    }
}

이번 문제는
1. 해당 자릿수에서 가능한 범위까지 탐색하고 그 중에서 가장 큰 수를 찾아 index 기억하기
ex) numbers가 9자리고 k가 3이라면 answer는 6자리이고, 첫번째 수는 0~3(k)까지 중에서 골라야 한다.
2. 다음 자릿수는 해당 index 다음 index부터 1번하기.
3. 앞에서 이미 answer를 다 찾은 경우 || 뒤에걸 다 취해야하는 경우 while문 빠져나오기

이 3단계 정도로 해서 풀었다.

그리고 나서 다른 방법을 찾아보았다.
뭔가 지저분해보여서..

import java.util.*;

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        Stack<Character> stack = new Stack<>();
        int len = number.length();
        int ans_l = len - k;
        for (int i = 0; i < len; i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0)
                stack.pop();
            if (stack.size() < ans_l)
                stack.push(c);
        }
        for (int i = 0; i < ans_l; i++)
            answer += stack.get(i);
        return answer;
    }
}

그리고 이런 깔쌈한 방법을 찾을 수 있었다.
스택을 이용한 방법이었다.. 왼쪽부터 차례대로 큰 수를.. 찾는 것이기 때문에 가능한..
k가 pop할 수 있는 기회의 수나 마찬가지인 것이다.

이게 그리디를 사용했을 때 걸리는 시간이고

이게 스택을 사용했을 때 걸리는 시간인데 1 ~ 6, 10 ~ 12 는 스택이 훨씬 빠르고,
7 ~ 9번만 그리디가 빠르다. 무슨 경우일까?
아마 추측컨데 이미 뒤에 남아있는 것을 다 취해야하는 경우인데,
계속 조건 검사를 하며 push하는 부분이 문제이지 않을까 싶었다.

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        Stack<Character> stack = new Stack<>();
        int i = -1, len = number.length(), ans_l = len - k;
        while (++i < len) {
            if (k < 0 && ans_l - stack.size() == len - i)
                break;
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0)
                stack.pop();
            if (stack.size() < ans_l)
                stack.push(c);
        }
        for (int j = 0; j < stack.size(); j++)
            answer += stack.get(j);
        if (answer.length() != ans_l)
            answer += number.substring(i, len);
        return answer;
    }
}