[JAVA] 탐욕법(Greedy) "큰 수 만들기"

k=3

k=2

k=1

k=0

https://programmers.co.kr/learn/courses/30/lessons/42883

 

값을 구하는 방식에 대해서 아이디어를 생각해내는 것이 어려워서 다른 이들의 코드를 참고했다.

 

• String에 저장된 숫자를 int값으로 추출해내는 테크닉 : .charAt(i)메소드 사용
• char 값에서 '0' 을 빼면 int값이 나오는 테크닉 : c - '0'
• Stack에서 배열처럼 가져오기 : .get(i)메소드 사용
• char배열을 String으로 변환하기 : char[] result = new [~];  return new String(result);

 

위와 같은 테크닉을 배울 수 있었다.

 

class Solution {
​​​​public String solution(String number, int k) {
​​​​​​​​char[] result = new char[number.length() - k];
​​​​​​​​Stack<Character> stack = new Stack<>();

​​​​​​​​for (int i=0; i<number.length(); i++) {
‌​​​​​​​​//String으로부터 char값으로 받을수있다.
​​​​​​​​​​​​char c = number.charAt(i);
​​​​​​​​​​​​
​​​​​​​​​​​​//설명 必
​​​​​​​​​​​​while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
‌​​​​​​​​​​​​//출력은 의미없다. pop에 의의를 두자.
​​​​​​​​​​​​​​​​System.out.println(stack.pop());
​​​​​​​​​​​​}
​​​​​​​​​​​​stack.push(c);
​​​​​​​​}
​​​​​​​​for (int i=0; i<result.length; i++) {
‌​​​​​​​​//get메소드를 이용하여 i번째 값을 갖고 올 수 있다.
​​​​​​​​​​​​result[i] = stack.get(i);
​​​​​​​​}
​​​​​​​​//char[]배열을 String으로 변환해서 반환한다.
​​​​​​​​return new String(result);
​​​​}
}

예시)

num: 4 1 7 7 2 5 2 8 4 1

idx:   0 1 2 3 4 5 6 7 8 9

k =4 일때 결과값은 길이가 10-4=6이다.

 

for문을 i 값에 따라서 돌려보겠다.

i=0, stack : 4

i=1, stack : 41

i=2, stack : 7 , pop:14 => k=3 =>k=2

i=3, stack : 77

i=4, stack : 772

i=5, stack : 775 , pop:2 =>k=1

i=6, stack : 7752

i=7, stack : 7758 , pop:2 => k=0 이니까 i=8부터는 조건문 패스

i=8, stack : 77584

i=9, stack : 775841