그리디 알고리즘 (Greedy Algorithm)

: 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘으로 최적의 해를 보장해주지 않는다.

예시

A 정점에서 F 정점까지 가는 방법을 찾을 때, A → B 가 A → D 보다 비용이 낮으므로 B 정점으로 가는 방법을 선택한다.
A → B → C → F 경로는 이동거리가 65, A → D → E → F 경로는 이동거리가 33이므로, 최종적으로는 최적의 해를 선택하지 못한다.

그리디 알고리즘의 특징

• 보통 최적의 해를 구하는 알고리즘보다 빠른 경우가 많다.
• 크루스칼, 다익스트라 알고리즘 등에 사용된다.
• 직관적인 문제 풀이에 적합하다.

---

그리디 문제 풀이

큰 수 만들기

문제 설명

어떤 숫자에서 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"

---

문제 풀이

지금 보고있는 숫자가 다음 숫자보다 크면 그냥 두고, 작으면 제거한다.

입출력 예 1)

numbers = 1924, k = 2

• 1과 9를 비교해서 1을 지운다. ➡️ 924
• 9와 2를 비교해서 2를 지운다. ➡️ 94
  94가 남는다. ⭕️

입출력 예 2)

numbers = 1231234, k = 3

• 1과 2를 비교해서 1을 지운다. ➡️ 231234
• 2와 3을 비교해서 2를 지운다. ➡️ 31234
• 3과 1을 비교해서 1을 지운다. ➡️ 3234
  3234가 남는다. ⭕️

입출력 예 3)

numbers = 4177252841, k = 4

• 4와 1을 비교해서 1을 지운다. ➡️ 477252841
• 4와 7을 비교해서 4를 지운다. ➡️ 77252841
• 7과 7을 비교해서 7을 지운다. ➡️ 7252841
• 7과 2를 비교해서 2를 지운다. ➡️ 752841
  752841이 남는다. ❌

스택 자료구조를 이용해서, 스택의 맨 위의 숫자보다 크면 그냥 두고, 작으면 스택 안에 자신보다 작은 수를 모두 제거한다.

입출력 예 1)

numbers = 1924, k = 2

• 스택에 1을 넣는다.
  stack = [1], count = 0 (k개 지워야하므로 몇 개 지웠는지 카운트)
• 스택에 9를 넣는다. 이때 스택 안에 9보다 작은 값은 전부 지운다.
  stack = [9], count = 1
• 스택에 2를 넣는다.
  stack = [9, 2]
• 스택에 4를 넣는다. 이때 스택 안에 4보다 작은 값은 전부 지운다.
  stack = [9, 4], count = 2 ⭕️

입출력 예 2)

numbers = 1231234, k = 3

• 스택에 1을 넣는다.
  stack = [1], count = 0
• 스택에 2를 넣는다. 이때 스택 안에 2보다 작은 값은 전부 지운다.
  stack = [2], count = 1
• 스택에 3을 넣는다. 이때 스택 안에 3보다 작은 값은 전부 지운다.
  stack = [3], count = 2
• 스택에 1을 넣는다.
  stack = [3, 1]
• 스택에 2를 넣는다. 이때 스택 안에 2보다 작은 값은 전부 지운다.
  stack = [3, 2], count = 3
• count === k가 되었다면 나머지 숫자들은 스택에 순서대로 넣는다.
  stack = [3, 2, 3, 4] ⭕️

입출력 예 3)

numbers = 4177252841, k = 4

• 스택에 4를 넣는다.
  stack = [4], count = 0
• 스택에 1을 넣는다.
  stack = [4, 1]
• 스택에 7을 넣는다. 이때 스택 안에 7보다 작은 값은 전부 지운다.
  stack = [7], count = 2
• 스택에 7을 넣는다.
  stack = [7, 7], count = 2
• 스택에 2를 넣는다.
  stack = [7, 7, 2]
• 스택에 5를 넣는다. 이때 스택 안에 5보다 작은 값은 전부 지운다.
  stack = [7, 7, 5], count = 3
• 스택에 2를 넣는다.
  stack = [7, 7, 5, 2]
• 스택에 8을 넣는다. 이때 스택 안에 8보다 작은 값은 전부 지운다.
  stack = [7, 7, 5, 8], count = 4
• count === k가 되었다면 나머지 숫자들은 스택에 순서대로 넣는다.
  stack = [7, 7, 5, 8, 4, 1] ⭕️

function solution(number, k) {
  const stack = [];
  let count = 0; // 몇 개 지웠는지 카운트할 변수를 만든다.
  
  for (const num of number) {
    while (count < k && num > stack[stack.length - 1]) { // stack 맨 위의 값보다 큰 값이 나오면,
      stack.pop(); // 이전 값 중 더 작은 값은 전부 다 삭제한다.
      count += 1;
    }
    stack.push(num); // 스택에 요소들을 순차적으로 넣는다.
  }
  
  while (count < k) { // 운이 좋게 스택이 순서대로 쌓여 카운트가 k까지 다 지워지지 않은 경우 e.g. 987654321
    stack.pop(); // k를 채울 때까지 요소를 삭제해준다.
    count += 1;
  }
  
  return stack.join('');
}