에잇퍼센트 알고리즘 면접문제 (핑퐁게임)


작성일 : 2017-01-16 19:58:49
조회수 : 1355


본문

이 문제는 구글링(링크)을 통해 알게 된 문제입니다. 공개된 문제는 다음과 같습니다.


일련의 숫자가 있고, 이 숫자는 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))

에잇퍼센트 알고리즘 면접문제 (핑퐁게임) - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.