[Java] 큰 수 만들기 (programmers)

0913

---

문제 설명

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

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

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

제한 조건

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

입출력 예

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

소스 코드

import java.util.Stack;
class Solution {
    public String solution(String numbers, int k) {
        //String answer = "";
        //결과를 담을 char배열 준비 - 주어진 숫자에서 k개의 자리를 뺀 만큼
        char[] result = new char[numbers.length() - k];
        //스택 자료구조를 준비
        Stack<Character> stack = new Stack<>();

        //주어진 숫자의 자리수만큼 반복
        for (int i=0; i<numbers.length(); i++) {
            //각 자리에 있는 문자를 읽어서
            char c = numbers.charAt(i);
            //스택에 내용이 있고
            //마지막에 넣은 값이 c보다 작고
            //아직 k개 만큼 숫자를 제거하지 않았다면
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                //스택에서 마지막에 넣었던 문자를 제거한다.
                stack.pop();
            }
            //스택에 더 이상 저장된 값이 없거나
            //스택 마지막에 있는 값이 c보다 크거나
            //이미 k개 만큼의 숫자를 제거했다면
            //스택에 c를 저장한다.
            stack.push(c);
        }
        //스택에 저장된 내용들을 result 배열에 저장한다.
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
            //answer += stack.get(i);
        }
        //만들어진 char배열을 String으로 변환해서 리턴.
        return new String(result);
    }
}

소스 풀이

    public String solution(String numbers, int k) {

숫자 number와 제거할 수의 개수 k를 외부에서 가져온다.

        //결과를 담을 char배열 준비 - 주어진 숫자에서 k개의 자리를 뺀 만큼
        char[] result = new char[numbers.length() - k];

결과를 담을 char배열을 준비한다.
주어진 숫자에서 k개의 자리를 뺀 만큼의 저장 공간을 할당한다.

        //스택 자료구조를 준비
        Stack<Character> stack = new Stack<>();

stack자료구조를 준비한다.
<>를 이용해 stack에 char형만 담을 수 있도록 준비한다.

		//주어진 숫자의 자리수만큼 반복
        for (int i=0; i<numbers.length(); i++) {
            //각 자리에 있는 문자를 읽어서
            char c = numbers.charAt(i);
            //스택에 내용이 있고
            //마지막에 넣은 값이 c보다 작고
            //아직 k개 만큼 숫자를 제거하지 않았다면
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                //스택에서 마지막에 넣었던 문자를 제거한다.
                stack.pop();
            }
            //스택에 더 이상 저장된 값이 없거나
            //스택 마지막에 있는 값이 c보다 크거나
            //이미 k개 만큼의 숫자를 제거했다면
            //스택에 c를 저장한다.
            stack.push(c);
        }

for문을 주어진 숫자의 자릿수만큼 반복한다.

c에 numbers에 들어있는 i번째 방의 자릿수를 저장한다.

stack.isEmpty는 stack에 내용이 없는지를 알아볼 수 있다. 여기에 !가 붙었으니 부정의 의미로 stack에 값이 있는지를 물어보는 것이다.

stack.peek()는 stack의 맨 위에 있는 값을 꺼내서 보는 것이다. 값을 스택에서 완전히 꺼내어 내는 것이 아니라 맨 위의 값만 본다는 뜻이다. 따라서 stack.peek() < c은 맨 마지막에 stack에 담긴 숫자가 c보다 작은지를 물어보는 것이다.

k-- > 0은 k가 0보다 크고, while문의 모든 조건을 충족했다면 k의 값을 1감소시키는 것이다. while문의 실행문의 내용은 stack의 맨 위의 값을 제거하고 c를 대신 넣는 것, 다시 말해 작은 수를 제거하는 것이기 때문에 수를 제거할 개수인 k를 --연산하는 것이다.

stack.pop();은 stack에 들어있는 맨 첫 번째의 값을 pop, 밖으로 꺼낸다는 의미이다.

while문의 조건에 맞다면 stack.pop()을 수행할 것이고, 조건에 맞지 않다면 while문을 지나쳐 stack.push(c)를 수행할 것이다.

stack.push(c)는 stack에 c의 값을 push, 즉 넣는다는 의미다.

        //스택에 저장된 내용들을 result 배열에 저장한다.
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
            //answer += stack.get(i);
        }

스택에 저장된 내용들을 result배열에 저장한다.

result에 순서대로 stack.get을 사용하여 result도 stack도 똑같이 i번째의 값을 저장한다.

        //만들어진 char배열을 String으로 변환해서 리턴.
        return new String(result);

만들어진 char배열을 String으로 변환해서 리턴한다. 이 때 String으로 리턴하기 위해 new String을 사용한다.

---