이 문제는 구글링(링크)을 통해 알게 된 문제입니다. 공개된 문제는 다음과 같습니다.
일련의 숫자가 있고, 이 숫자는 1씩 증가, 또는 감소한다. n번째의 숫자가 있을 시에, 이 숫자가 7의 배수(7, 14, 21,...)거나 7이란 숫자를 포함할 시에 (7, 17, 27,...) 방향을 바꾼다.
즉, 1, 2, 3, 4, 5, 6, [7], 6, 5, 4, 3, 2, 1, [0], 1, 2, [3], 2, 1, 0, [-1], 0, 1
과 같이 숫자는 진행한다. (첫 번째 7은 7번째, 두 번째 0은 14번째, 세 번째 3은 17번째, 네 번째 -1은 21번째)
다음의 제약 하에 pingpong(x)의 함수를 작성하라. 예시의 인풋과 아웃풋은 다음과 같다.
pingpong(8) = 6
pingpong(22) = 0
pingpong(68) = 2
pingpong(100) = 2
반드시 Python 언어를 이용하여 풀 것.
For Loop 또는 Array 를 쓰지 말 것.
Assignment 를 쓰지 말 것. 즉, 변수 할당을 하지 말 것.
String 을 쓰지 말 것.
조건이 상당히 까다로운 문제입니다. 새로운 변수를 할당할 수 없고, for문 과 배열, string까지 사용할 수 없으니 말이죠. 이 문제는 어떻게 접근해야 할까요? 우선 for loop와 같은 iterate 적인 접근을 하지 말라고 하였으니 면접에서 자주 등장하는 recursive function을 이용해야 함을 짐작할 수 있고, 변수 할당을 하면 안 되므로 숫자가 증가 상태인지 감소 상태인지를 다른 방법으로 판단해야 함을 알 수 있습니다. 그리고 Array와 String을 사용할 수 없습니다.
숫자가 증가 상태인지 감소 상태인지를 알기 위해서는 숫자를 증가시키는 재귀함수와 숫자를 감소시키는 재귀함수의 2개로 분리하는 것이 필요함을 알 수 있습니다. 숫자가 7의 배수인지 확인하기 위해서는 임의의 k에 대해 k%7==0 임을 통해 알 수 있습니다. k%7==0 정도는 허용되는 것을 보니, 숫자에 7이 포함되어 있는지 확인하는 것도 약간의 노가다를 통해 알 수 있습니다.
가장 중요한 이 문제의 시간 복잡도 입니다. 비록 이 문제의 n의 max는 1000이지만, 우리는 최적의 시간으로 이 프로그램을 작성한다고 합시다, 이 문제는 1번째 원소부터 시작해 n번째 원소에 대해 증가, 감소 상태만 알 수 있다면 그 다음 재귀 호출에 +1, -1만 하면 되므로 $O(n)$에 해결할 수 있음을 알 수 있습니다.
숫자를 증가시키는 재귀함수를 $pdfs$, 감소시키는 재귀함수를 $mdfs$라고 정의 하였습니다. 완성된 소스는 다음과 같습니다.
n = int(input())
def pdfs(k):
if(k>n):
return 0
if(k%7==0 or k%10==7 or int(k/10)%10==7 or int(k/100)%10==7 or int(k/1000)%10==7):
return mdfs(k+1)+1
else:
return pdfs(k+1)+1
def mdfs(k):
if(k>n):
return 0
if(k%7==0 or k%10==7 or int(k/10)%10==7 or int(k/100)%10==7 or int(k/1000)%10==7):
return pdfs(k+1)-1
else:
return mdfs(k+1)-1
print(pdfs(1))