Sho1007

MMORPG 클라이언트 개발자 지망생

2 minute read

402. Remove K Digits / c++ / Medium / 46분

문제 및 코드

class Solution {
public:
    string removeKdigits(string num, int k) {
        if (num.length() == k) return "0";
        int removeCount = 0;
        
        for (int i = 0; i < num.length() - 1;)
        {
            // cout << removeCount << " : " << num << '\n';
            if (i == 0 && num[i] == '0')
            {
                num.erase(num.begin());
                continue;
            }

            if (num[i] > num[i+1])
            {
                if (removeCount< k)
                {
                    removeCount++;
                    num.erase(num.begin() + i);
                    if (i > 0) i--;
                    continue;
                }
            }
            i++;
        }

        num = k - removeCount >= num.length() ? "" : num.substr(0, num.length() - (k - removeCount));

        return num.length() > 0 ? num : "0";
    }
};

접근 방식

문자열

  1. 처음엔 완전탐색과 백트래킹으로 k개 만큼 제거한 뒤에 배열에 넣어서 정렬 후 최소값을 찾아볼까 했다.
  2. 하지만 k와 num의 길이의 최대값은 10^5였고 1번 방식으로 풀다간 시간 / 공간 복잡도가 엄청 늘어남은 물론이고 해당 숫자를 담을 자료형 조차 없었다.
  3. 그래서 단순 숫자대 숫자로 비교가 안된다는 것을 깨닫고, 그럼 문제를 풀기 위해선 규칙이 있을 것이라고 판단했다.
  4. 첫 번째로 찾은 규칙은 이러했다. 만약 현재 자리의 수가 다음 자리의 수보다 크다면 제거하는 것이다.
    (ex. 1243 에서 하나를 제거한다고 했을 때, 123이 제일 작은 수이다. 즉 4가 3보다 크므로 4를 제거하는 것이 정답이다.)
  5. 4번 규칙대로 풀었더니 1234567890 에서 결과가 123456780 이 나왔다. i + 1에 접근해야 해서 for 문의 규칙을 i < num.length() - 1로 걸었더니, 9가 제거되면서 num의 길이가 하나 줄어서 i < num.length() - 1 에 걸려서 종료된 것이었다.
  6. 5번을 해결하기 위해 한 자리를 제거할 때, i 도 1 감소시켜줬다. 그러면 1234567890에서 9를 제거하면 num[i]는 0이 아닌 8을 가리키게 되므로, 연쇄적으로 num[i] > num[i+1] 조건문을 통해 연쇄적으로 줄여나갈 수 있게 된다.
  7. 다음 문제는 6번까지의 for문 순회를 돌고 난 다음 removeCount(제거한 횟수)가 k보다 작아서 생기는 문제였다. 예를 들어 11111 처럼 다 같은 문자여서 조건식에 걸리지 않았던가, 10001 처럼 중간에 0이 들어가서 자동적으로 탈락된 경우 (이 경우엔 자동 탈락이므로 removeCount는 증가하지 않는다.), k = 5 일 때 둘 다 정답은 0이 나와야 했다.
  8. 7번 문제점을 해결하면서 한가지 추가적인 규칙을 찾아냈다. for문 순회가 끝난 수를 보면 마치 12345 처럼 정렬된 모양새를 띈다는 점이었다.
  9. 그래서 이 경우엔 앞에서 제거하는게 아닌, 뒷부분을 제거하는 것이 결과값을 줄이는 방법이었다.
  10. 따라서 만약 k - removeCount (남은 제거 횟수)가 만약 현재 num의 길이보다 크거나 같다면, 다 지워야하는 경우이므로 num을 “” 로 만들어줬고 (이 경우 반환 과정에서 “0”으로 치환된다.), 그게 아니라면 num을 num.length() - (k - removeCount)로 만들어줬다. (num을 뒤에서부터 남은 제거 횟수만큼 제거한 부분 문자열)
  11. 해결

생각해 볼 점

  1. medium 난이도 치고는 생각보다 풀이시간이 오래 걸렸다. (역시나 난 문자열에 약한 것 같다.)
  2. leetcode는 틀린 케이스를 자꾸 알려줘서 거기에 맞춰서 풀게되는 느낌이다. (내가 찾아낸 것들도 있지만 생각하지 않은 엣지 케이스를 알려줘서 뇌 빼고 보는 느낌)
  3. 그래도 99클럽을 시작한 뒤로 꾸준히 하루 한 문제씩 풀면서 문제 해결 능력도 많이 올라온 것 같다.
  4. 단적인 예로 이런 막히는 문제들도 이제는 다른 사람들의 풀이를 보지 않고 혼자 해결할 수 있게 되었다. (특히 내 약점인 문자열 문제였음에도)
  5. 또한 오늘 내 글이 우수 TIL로 선정되었다는 공지가 올라왔고 성취감이 배로 늘었다.
  6. 다시 한번 이런 커리큘럼을 만들어준 팀스파르타에 감사함을 느낀다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL

You may also enjoy