[프로그래머스] 큰 수 만들기 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

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

2. 입력

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

3. 예제

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

4. 풀이

입력으로 주어진 수에서 k개의 수를 제거하였을 때 가장 큰 수를 만드는 것이므로 입력으로 주어진 수에 대한 순서는 변화가 없어야 하기에 Stack을 이용하여 문제를 풀었습니다.

 

Stack의 상태에 따라 필요한 작업이 달라집니다.

• Empty인 경우 : Empty인 경우는 현재 Stack에 아무런 수가 없으므로 무조건 Stack에 숫자를 집어넣습니다.
• Emtpy가 아닌 경우 : Empty가 아닌 경우는 현재 Stack에 입력하고자 하는 숫자보다 작은 숫자가 이미 들어 있다면 큰 수를 만들기 위해 지워야 하는 수가 됩니다.
  
  그러므로 Stack을 순회하면서 입력하고자 하는 수 보다 작은 수를 모두 지워 줍니다.
  
  단 우리가 지울 수 있는 수의 개수가 정해져 있으므로 지울 수 있는 개수만큼만 지우도록 합니다.

이렇게 Stack이 모두 구성이 되었습니다.

 

이제 남은 작업은 만약 위 Stack을 구성하기 위해 지운 숫자의 개수가 k보다 작다면 남은 개수만큼 Stack에서 지우는 작업을 해야 됩니다.

 

즉 입력된 k가 6 인대 Stack을 구성하기 위해 지운 문자가 3개라면 추가로 지워야 하는 개수가 3개가 남아 있으므로 구성된 Stack에서 3개의 문자를 지워 줍니다.

 

이후 Stack에서 숫자들을 꺼내어 하나의 문자열로 만들어 주면 숫자는 완성이 됩니다. 이때 Stack의 경우는 숫자들이 역순으로 들어 있으므로 하나의 문자열로 만든 뒤 reverse 시켜 정답을 완성하면 됩니다.

5. 코드

전체 코드는 Git에 있습니다.

Stack<String> stack = new Stack<>();

for (int i = 0; i < number.length(); i++) {
	while (!stack.isEmpty()) {
		if (Integer.parseInt(stack.peek()) < Integer.parseInt(number.substring(i, i + 1)) && k != 0) {
			stack.pop();
			k--;
		} else
			break;
	}

	stack.push(number.substring(i, i + 1));
}

for(int i=0; i<k; i++)
	stack.pop();

StringBuilder stringBuilder = new StringBuilder();

while(!stack.isEmpty())
	stringBuilder.append(stack.pop());

return stringBuilder.reverse().toString();