C++에서 K 자리 제거

문자열로 표현되는 음이 아닌 정수 숫자가 있다고 가정하면 새 숫자가 가능한 가장 작도록 숫자에서 k 자리를 제거해야 합니다. 따라서 입력이 "1432219"이고 k =3이면 결과는 "1219"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 스택 st를 정의하고 빈 문자열 ret를 만듭니다.

• n :=숫자 크기

• 0 ~ n – 1 범위의 i에 대해

  • k는 0이 아니고 스택은 비어 있지 않고 스택의 맨 위> num[i]

    • 스택에서 삭제하고 k를 1 감소

  • num[i]를 st

    에 삽입

• k가 0이 아닌 동안 스택에서 요소 삭제

• 스택이 비어 있지 않은 동안

  • ret :=ret + 스택의 맨 위, 스택에서 요소 삭제

• 이제 ret 문자열을 뒤집습니다.

• ans :=빈 문자열, 그리고 i :=0

• 반면 i

  • i를 1 증가

• 나는 에 대해

  • ans :=ans + ret[i]

• ret :=ans

• ret의 크기가 0이면 "0"을 반환하고, 그렇지 않으면 ret

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution {
public:
   string removeKdigits(string num, int k) {
      stack st;
      string ret = "";
      int n = num.size();
      for(int i = 0; i < n; i++){
         while(k && !st.empty() && st.top() > num[i]){
            st.pop();
            k--;
         }
         st.push(num[i]);
      }
      while(k--)st.pop();
      while(!st.empty()){
         ret += st.top();
         st.pop();
      }
      reverse(ret.begin(), ret.end());
      string ans = "";
      int i = 0;
      while(i <ret.size() && ret[i] == '0')i++;
      for(; i < ret.size(); i++)ans += ret[i];
      ret = ans;
      return ret.size() == 0? "0" : ret;
   }
};

입력

"1432219"
3

출력

"1219"