2022-01-03 / 큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

 

 

제한 조건

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

 

 

입출력 예

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

 

 

기본 코드

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        return answer;
    }
}

 

 

정답 코드

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

  for (int i = 0; i < number.length()-k; i++) {
    char max = '0';
    for (int j = index; j <= k + i; j++) {
        char tmp = number.charAt(j);
        if(max < tmp) {
            max = tmp;
            index = j + 1;
        }
        }
        answer.append(max);
    }

    return answer.toString(); 
    }
}

 

 

 

 

---

 

 

 

문자열 중에서 k 개수만큼 작은 수를 찾아서 문자열에서 지운 값을 찾는 문제이다.

index는 number를 몇번째부터 체크할지 정하는 변수이다. 

반복문을 문자열 길이- k만큼 돌리는 이유는 최종 문자열의 길이가 k 개수만큼 뺀 길이이기 때문이다.

문자열 중에서 최댓값을 찾으면 해당 값의 위치 다음부터 다시 체크한다.

 

 

 

 

처음에는 문제를 잘못 이해해서 단순히 split으로 배열에 넣은 후 정렬해서 뺀 값을 가져오면 되는 줄 알았다. 하지만 원래의 문자열 순서를 지켜야하고 또 시간 초과도 체크해야하기 때문에 아예 틀렸다. 풀이를 찾아보니 스택을 사용한 사람들도 많던데 얼른 공부해야겠다.. 스택으로 가능하면 ArrayList도 되지 않을까? 저장되는 순서가 달라서 안되려나 쩝