처음에는 문제를 보고 어렵게 생각했다.
각 자리 숫자를 보고 변경이 필요한 부분을 생각하고 위와 같이 짰는데 3434가 input으로 들어갈 경우 404라는 기이한 숫자가 출력되었다.
나는 숫자를 하나씩 줄이면서 확인하면 시간복잡도 문제에 걸릴 거라고 생각하여 위와 같이 생각했는데 오히려 계산이 복잡해진 것이다.
구글링을 하여보니 대다수의 사람들이 작성한 코드는 입력 받은 숫자에서 4와 7이 포함되지 않은 경우 하나씩 줄여가며 확인을 하는 코드를 작성한 것을 알 수 있다. 아래와 같이 말이다.
그렇다면 위 코드의 시간복잡도를 계산해보자
일단 while 문 안에서 for 문이 중첩되어 있기에 O(nlogn). for문으로만 중첩반복문이 이루어진 것보다는 시간복잡도 면에서 좋은 편이다. 그랬기에 시간초과의 문제 없이 위 코드로 해결할 수 있었다.
