[탐욕법] 큰 수 만들기

Problem. 큰 수 만들기

---

Link.

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

프로그래머스

---

Problem.

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

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

이 중 가장 큰 숫자는 94입니다.

 

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다.

number에서 k개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하시오.

 

제한사항

1. number는 2자리 이상, 1,000,000자리 이하인 숫자

2. k는 1 이상 number의 자릿수 미만인 자연수

 

입출력 예시

// case#1
number = "1924";
k = 2;
return = "94";

// case#2
number = "1231234";
k = 3;
return = "3234";

// case#3
number = "4177252841";
k = 4;
return = "775841";

---

In Details.

Case#1

number = "1924", k = 2

 

첫번째 Iteration

num이 1이고

while문의 조건문이 false이므로 stack에 1만 넣어준다.

따라서 stack = [1], count = 0 이다.

// 첫번째 iteration
num = 1;
count = 0;

for (let num of number) {
    while (0 < 2 && null < num) { // true && false -> false
        stack.pop();
        count++;
    }
	stack.push(num); // [] -> [1]
}

 

두번째 Iteration

num이 9이고

while문의 조건문이 true가 되므로 while문 내부 로직을 한 번 돌게 된다.

stack = [9], count = 1 이다.

// 두번째 iteration
num = 9;
count = 0;

while (0 < 2 && 1 < 9) { // true && true -> true
	stack.pop(); // [1] -> []
    count++; // 0 -> 1
}
stack.push(num); // [] -> [9]

 

세번째 Iteration

num이 2이고

while문의 조건문이 false이므로 stack에 2만 넣어준다.

stack = [9, 2], count = 1 이다.

// 세번째 iteration
num = 2;
count = 1;

for (let num of number) {
    while (1 < 2 && 9 < 2) { // true && false -> false
        stack.pop();
        count++;
    }
    stack.push(num); // [9] -> [9, 2]
}

 

네번째 Iteration (마지막)

num이 4이고

while문의 조건문이 true가 되므로 while문 내부 로직을 한 번 돌게 된다.

stack = [9, 4], count = 2 이다.

 

모든 문자열을 순회했으므로 for문을 종료한다.

// 네번째 iteration
num = 4;
count = 1;

for (let num of number) {
    while (1 < 2 && 2 < 4) { // true && true -> true
        stack.pop(); // [9, 2] -> [9]
        count++; // 1 -> 2
    }
    stack.push(num); // [9] -> [9, 4]
}

---

My Answer. 

function solution(number, k) {
    // stack 정의
    const stack = [];
    // 숫자를 제거한 횟수를 카운트 할 변수
    let count = 0;
    
    for (let num of number) {
        // 제거한 횟수(count)가 제거할 횟수(k)보다 작고
        // num이 stack에 마지막 숫자보다 큰 경우
        // stack이 비어있는 경우 -> stack[stack.length - 1] = undefined
        // undefined < num -> false
        while (count < k && stack[stack.length - 1] < num) {
            // stack에 마지막 숫자 제거
            stack.pop();
            // 제거한 횟수 +1;
            count++;
        }      
        stack.push(num);
    }
    
    // count가 k보다 작은 경우 -> 추가적으로 stack pop 실행
    while (count < k) {
        stack.pop();
        count++;
    }
    
    return stack.join("");
}

---

References.

• 코딩테스트 광탈 방지 A to Z: JavaScript (이선협)

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)