Sho1007

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

3 minute read

738. Monotone Increasing Digits / c++ / Medium / 18분

문제 및 코드

문제 링크

bool CheckMID(string current)
{
    for (int i = 1; i < current.length(); ++i)
    {
        if (current[i-1] > current[i]) return false;
    }

    return true;
}
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string current = to_string(n);

        // n보다 작거나 같은 증가하는 수 (붙어있는 두 자리 ij가 i<=j인 수)를 구하시오
        // 만약 n이 증가하는 수면? return
        // 만약 n이 증가하는 수가 아니라면? 감소 -> 어떻게?

        if (CheckMID(current)) return n;

        for (int i = current.length() - 1; i > 0; --i)
        {
            if (current[i] < current[i-1])
            {
                for (int j = i; j < current.length(); ++j)
                {
                    current[j] = '9';
                }
                current[i-1]--;
            }
            // cout << current << '\n';
        }

        return stoi(current);
    }
};

접근 방식

그리디

  1. n보다 작거나 같은 단조롭게 증가하는 수 중 가장 큰 수를 반환하는 문제였다.
  2. 저 단조롭게 증가하는 수 가 뭔지 와닿질 않아서 검색해보니 인접한 두 자리의 수를 ij라고 할 때, (i <= j) 를 만족하는 수였다. (즉, 이전자리가 다음자리 보다 작거나 같아야 한다.)
  3. 큰 흐름을 봤을 때, 일단 n이 단조롭게 증가하는 수 (줄여서 MID 라고 부르겠다.) 라면 그대로 n을 반환한다.
  4. n이 MID가 아니라면 n보다 작은 MID 중 가장 큰 수를 반환하면 된다고 생각했다.
  5. 그러면 우선 MID인지를 판단하는 식이 필요했고, 임의의 숫자 current의 각자리를 돌면서 현재 자리가 다음 자리보다 크면 false, 모든 자리가 다음 자리보다 작거나 같으면 true를 반환하는 CheckMID를 만들었다. (그리고 각 자리의 비교를 편하게 하기 위해 string current = to_string(n) 를 사용했다.)
  6. n이 MID라면 그대로 n을 반환
  7. 이제 n이 MID가 아닐 때, n보다 작은 수 중 가장 큰 MID를 찾는 규칙이 필요했다.
  8. 이럴 땐, 임의의 수들이 변화는 과정을 보는게 효율적이라고 생각했다. 우선 예제에 있는 수 중 1234는 이미 MID이므로 이걸 1243으로 바꿔봤다. 그러면 답은 1239가 나온다. 그리고 10을 넣으면 9가 답으로 나온다. 여기서 찾은 규칙은 MID가 아니라면, i <= j 가 아닌 부분이 9로 바뀐다는 점이었다.
  9. current[i] > current[j] 이면, MID를 만들기 위해 current[i]가 1 감소해야하는데, 이 때, 결과값 current가 MID 중 가장 큰 수가 되려면 다음 자리인 current[j]는 9가 되어야했다.
  10. 여기서 어느정도 결과를 찾았고, current를 끝 (가장 작은 자리)부터 순회하면서, MID를 만족하지 않는 부분에서 current[i]는 1을 감소시키고, current[i+1] 은 9로 만들어줬다. 그러면 i가 한칸씩 앞으로 가면서 모든 자리의 MID를 맞추게 된다고 생각했다.
  11. 그리고 나서 엣지 케이스를 체크하기 위해 n의 범위의 양 끝 값인 0과 1’000’000’000을 TestCase에 넣어봤다.
  12. 0의 경우 값이 잘 나왔지만, 1’000’000’000의 경우 기대값은 999’999’999인데 결과값은 900’000’000이 나왔다.
  13. 왜인지 원인을 찾아보니, MID를 만족하지 않는 부분에서 current[i]는 1 감소, current[i+1]은 9로 만들어줬지만, i + 2, i + 3, … , current.length() - 1 까지의 값은 그대로였던 것이 문제였다.
  14. 즉, 앞으로는 연쇄가 일어났지만, 뒤로는 연쇄가 일어나지 않았다. (1’111은 999가 되지만, 1’000은 900이 되어버림)
  15. 그래서 새로운 규칙을 추가해줬다. MID를 만족하지 않는 부분이 생기면 그 뒤의 값을 다 9로 만들어줬다.
  16. 해결

생각해 볼 점

  1. 다시 생각해보니 monotoneIncreasingDigits 함수에서 for문을 돌때, 변환이 일어나지 않았다면 n이 이미 MID이므로 CheckMID함수는 만들 필요가 없었다.
  2. 항상 엣지케이스를 많이 놓쳤었는데, 이번에 스스로 엣지케이스 검사를 통해 새로운 규칙을 찾아서 문제를 해결하는 경험을 했다.
  3. 어느덧 40일이라는 시간이 지났고 99클럽 2기도 마무리되었다. 정말 어떻게 흘러갔는지 모를 시간이었고, 만약 99클럽을 신청하지 않았다면 분명 나는 이렇게 열심히 코테 준비와 TIL 작성을 하지 않았을 것이라고 생각한다.
  4. 99클럽 덕분에 꾸준히 하루에 1문제씩 풀 수 있었고, TIL을 적으면서 내가 풀었던 문제를 돌아보고 다시 정리할 수 있었다.
  5. 난 99클럽을 진행하면서 꾸준히 하는 습관과 코딩 테스트 능력을 기를 수 있었고, 다음 99 클럽 3기가 시작된다면 또 신청할 생각이다.
  6. 주변에도 간증처럼 내 얘기를 하면서 99클럽을 신청하라고 하는데, 생각보다 사람들은 잘 참여를 안한다. (효과 좋은데..)
  7. 99클럽을 만들어주신 팀 스파르타와 40일동안 관리해주신 매니저님들, 클럽장님들 정말 수고 많으셨습니다. 제가 비록 기타언어인 C++이고, 문제를 푸는 시간이 오후 10시 이후라 문제 풀이 세션을 참석 못(안)할 때가 더 많았지만 그래도 항상 문제 출제해주시고 관리해주신 덕분에 완주할 수 있었습니다. 이 글을 보실진 모르겠지만 다시 한번 감사하다는 말씀 드리고 싶습니다.
  8. 언젠가 C++도 정규 언어가 되는 날을 기대하며 이만 99클럽 2기 마지막 TIL을 마친다.

학습 기록

99클럽 2기 학습 기록

해시태그

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

You may also enjoy