42883: 큰 수 만들기[그리디]

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

---

1. 문제

• 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
  예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
  문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

---

2. 문제의 조건

• 1 <= n <= 1,000,000
• 1 <= k < n의 자리 수

 

---

3. 문제 접근

• 시간 복잡도
  
  시간 제한 1초에 계산해야 할 자리수는 100만 자리입니다. O(N^1.333)이내의 시간에 풀어야 가능 한 문제라고 생각합니다.

 

• 아이디어
  
  만약 n=4177252841 k=4 로 주어져있다면
  
  

  4

  1

  7

  7

  2

  5

  2

  8

  4

  1

  총 4자리를 뽑아야합니다. 이 경우 뽑을 수 있는 수는 8 4 1를 제외한 나머지 수입니다.
  (만약 8 4 1를 뽑게되면 결코 4자리를 만들 수 없음)
  이 상태에서 제일 큰 수
  
  

  4

  1

  7

  7

  2

  5

  2

  8

  4

  1

  만약 4번째의 7을 뽑게된다면 다음 수를 뽑을땐
  
  

  4

  1

  7

  7

  2

  5

  2

  8

  4

  1

  4번째를 제외한 [2, 5, 2, 8]중 뽑아야합니다.
  (위와 마찬가지로 4번째는 이미 뽑혔으니 이전으로는 다시 돌아갈 수 없고,
  나머지 자리수를 뽑으려면 최소한 2자리는 남겨두고 뽑아야 하기때문)
  
  이 때, 문제가 발생합니다.
  4번째 7을 고르게되면서 3번째의 7을 고를 수 없게 된 것입니다.
  그러므로 같은 숫자가 나란히 있을 땐 0과 가까운 idx를 뽑아야합니다.
  이런 식으로 계속 range를 조정해가면서 뽑으면 됩니다.
  
  즉, 시간복잡도는 O(N^2)이 됩니다.
  출제자가 TestCase가 부족하여 통과가 되는 오류인 듯합니다.

---

4. 풀이 방법

• 0부터 length = n의 자리수 - k 개만큼 돌려줍니다.
  (5자리에 k가 2이면 3자리를 뽑아야 하기 떄문)
• 현재의 stack부터 length + i 만큼 탐색합니다
  (range의 조정 부분)
• 만약 이전 값보다 더 큰 값이 있다면 index와 함께 집어넣습니다.
• stack은 뽑힌 숫자를 넣고 index + 1 위치부터 다시 탐색합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/79

 

---

 

cjw.git@gmail.com