8퍼센트 면접문제 - pingpong

8퍼센트 면접문제 - pingpong

문제

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

For Loop 또는 Array를 쓰지 말 것.

Assignment를 쓰지 말 것. 즉 변수 할당을 하지 말 것.

String을 쓰지 말 것.

풀이

▶ pingpong1

일단 제약조건이 까다롭다. "assignment를 쓰지 말 것"을 보면, 어쨋든 결과는 저장해야 할 텐데 대입을 하지 않고 가능한 방법은 재귀함수가 생각이 난다.규칙은 간단하다. 이전 값에 방향에 따라 +1 또는 -1을 해주면 된다. 재귀의 탈출은 1일 경우 1을 반환하고 나머지의 경우 n-1의 값에 방향값을 더해준다.이 때 방향을 계산해야 하는데 방향 또한 이전 값에 따라 달라지게 되므로 동일하게 재귀가 필요해 보인다. 이전 값이 7의 배수 또는 7을 포함하는 수면 이전 방향에 반대로, 아니면 그대로 사용해야 한다.또 string을 쓰지않고 7을 포함하는 수를 판단하려면 10으로 계속 나눠가면서 1의 자리가 7인지를 확인하면 되는데 마찬가지로 재귀를 사용한다.

▶ pingpong2

pingpong1을 계산하면서 각 항마다 방향을 구하는데 재귀로 되어 있기 때문에 매번 같은 계산이 반복된다. 즉 x가 10이면 10~7, 9~7, 8~7을 매번 재귀로 돌게 된다. (재귀의 탈출 조건을 7이하로 잡았기 때문에)100을 구할 때 _direction이 호출되는 횟수를 출력해 보면 4464(100일 경우 94번 ~ 8일 경우 1번, 7부터는 x를 반환하므로)가 나온다. 내부는 간단하지만 반복이 그만큼 많다는 의미로 시간 복잡도 면에서보면 O(n^2)이 된다. (n을 x값으로 할 때)pingpong과 마찬가지로 방향도 이전 방향에 따라 달리지기 때문에 매번 각 항목의 방향을 계산하지 않고 이전 방향값을 사용하도록 변경하면 그 부분을 제거 할 수 있다. 즉 pingpong을 x부터 거꾸로 구하기 때문에 이전값이 나중에 계산되어 반영하지 못하지만 반대로 1부터 x로 올라가면서 계산을 하면 이전 방향값을 사용할 수 있다.그러기 위해서는 탈출 조건으로 사용할 x값과 현재 순서, 값, 방향 등이 함수로 전달되야 한다. 7의 배수와 포함여부는 동일하게 사용하고 나머지만 변경했다. x는 최종값, n은 1부터 현재 순서, prevValue는 이전 순서의 값, direction은 현재 순서의 방향값이다.

▶ pingpong3

위 함수를 만들고 나니 반복문으로도 가능할 것 같은 느낌이 들었다. 그래서 일단 수정했으나 결국 assignment를 사용해야 했는데,,, 아마 추가적인 변수 할당을 금지하는 것이 아닐까 자의적으로 판단하고 매개변수 연산은 괜찮겠거니 하고 혼자 이해를...했다... x는 동일하게 최종값, n은 1부터 현재 순서, value는 현재 순서 값, direction은 현재 방향값이다.