숫자 피라미드 패턴 in Python

 

최근 모(?) 게시판에 N게임사 직원 python 코딩 문의 글.

찾아보니 'pyramid patterns' 출력 문항인데 완전 똑같은 문제는 검색이 잘 안되네.

이 문제다!

Input: 5 Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 7 8 9 10 4 5 6  2 3 1

 

 

내 코드 : n=4000일때 약 2~3초. 대충 짱구 굴려서... 

def func_jjh(n):
    i = 1
    count = 0
    line = ''
    num_stack = []
    line_stack = []
    reverse = False

    while True:
        line = ''
        if (reverse):
            line = line_stack.pop()
        else:
            num_stack.append(i)
            i += 1
            if (len(num_stack) == count + 1):
                line = " ".join(str(x) for x in num_stack)

        if (len(line) > 0):
            print(line)
            if reverse == False:
                count += 1
                if (count == n):
                    reverse = True
                else:
                    line_stack.append(line)
                num_stack = []

        if (len(line_stack) == 0):
            break

 

 

 

S전자 개발자 : 둘 다 n=4000일 때 약 3초 소요.

def f(n):
    cur = 1
    base = 1
    d = 1
    while cur > 0:
        for i in range(base, base+cur):
            print(i, end=' ')
        if cur == n: d=-1
        if d > 0: base += cur*d
        cur += d
        if d < 0: base += cur*d
        print('')

def f(n):
    cur = 1
    d = 1
    while cur > 0:
        st = int(cur * (cur-1)/2+1)
        for i in range(st, st+cur):
            # python3
            #print(i, end=' ')
            # python2
            print(i),
        if cur == n: d=-1
        cur += d
        print('')

 

 

 

N사 포털 개발자 : 한줄 짜리. 멋져보여도(?) n=300일때 3초, 500일때 16초, 600일때 22초,... 

분석은 하지 않겠다. 보기가 싫어지네 -_-;;

from functools import reduce
def f(n):
    print reduce(lambda a, b: ''.join(a)+"\n"+' '.join(b), [[str(i) for i in xrange(j*(j-1)/2 + 1, j*(j+1)/2 +1)] for j in [-abs(x-n)+n for x in xrange(1, 2*n)]])

 

 

 

L전자 개발자 : n이 997일때 1초, 998일때 최대 재귀 깊이에 도달.  
"RuntimeError: maximum recursion depth exceeded while getting the str of an object"

def func(n):
    def f_util(start, width, n):
        if width > n:
            return
        print_range(start, start + width)
        f_util(start + width, width + 1, n)
        if width < n:
            print_range(start, start + width)

    def print_range(lo, hi):
        for i in range(lo, hi):
            print(i),
        print

    f_util(1, 1, n)

현재 상태를 살펴보고 이 깊이를 크게 늘려보자. 아래와 같이 할 때 약 3~4초

import sys
len = sys.getrecursionlimit()
print(len) ## 1000이 나오네
sys.setrecursionlimit(len*10000) ## 임의로 만배 늘려놓고

def f(n):
    def f_util(start, width, n):
        if width > n:
            return
        print_range(start, start + width)
        f_util(start + width, width + 1, n)
        if width < n:
            print_range(start, start + width)

    def print_range(lo, hi):
        for i in range(lo, hi):
            print(i),
        print

    f_util(1, 1, n)

이번에는 print_range를 아래와 같이 변경하면 1~2초로 단축됨.

def f(n):
    def f_util(start, width, n):
        if width > n:
            return
        print(' '.join(map(str, range(start, start + width))))
        f_util(start + width, width + 1, n)
        if width < n:
            print(' '.join(map(str, range(start, start + width))))
    f_util(1, 1, n)

 

 

 

S사 개발자

  - Recursive 형태 : 이것 역시 n이 998일때 최대 재귀 깊이 도달

    "RuntimeError: maximum recursion depth exceeded while getting the str of an object"

def f(n, start=1, width=1):
    print(' '.join(map(str, range(start, start+width))))
    if width == n: return
    func_g(n, start + width, width + 1)
    print(' '.join(map(str, range(start, start + width))))

maximum recursion depth를 크게 늘려놓고, n=4000일 때 약 2초. 

import sys
len = sys.getrecursionlimit()
print(len) ## 1000이 나오네
sys.setrecursionlimit(len*10000)
    
def f(n, start=1, width=1):
    print(' '.join(map(str, range(start, start+width))))
    if width == n: return
    func_g(n, start + width, width + 1)
    print(' '.join(map(str, range(start, start + width))))

 

  - Iterative 형태 : n=4000일때 1~2초. (현재까지 가장 빠른느낌?)

def f(n):
    width = 1
    stack = [1]
    while len(stack) < n:
        print(' '.join(map(str, range(stack[-1], stack[-1] + width))))
        stack.append(stack[-1] + width)
        width += 1
    while stack:
        print(' '.join(map(str, range(stack[-1], stack[-1] + width))))
        stack.pop()
        width -= 1

 

 

N게임사 개발자

 f(4000)일 때 약 4초. 

def g(n):
    first = n * (n + 1) // 2 + 1
    for i in range(n + 1):
        print(first + i),
    print

def f(n):
    for i in range(n):
        g(i)
    for i in range(n-2, -1, -1):
        g(i)

 

 

 

---

map을 배웠으니 내 코드를 포함해서 다른 사람들 것 까지 iteration을 map을 활용해본다.

 

 

S전자 개발자 코드 보완 : 1~2초로 단축. (python2/3차이 구분), f_b는 큰 변화가 없는 것 같기도..

def f_a(value):
    cur = 1
    base = 1
    d = 1
    while cur > 0:
        line = ' '.join(map(str, range(base, base+cur)))
        #line = ' '.join([`num` for num in range(base, base+cur)])
        if cur == value: d=-1
        if d > 0: base += cur*d
        cur += d
        if d < 0: base += cur*d
        print(line)

def f_b(value):
    cur = 1
    d = 1
    while cur > 0:
        st = int(cur * (cur-1)/2+1)
        line = ' '.join(map(str, range(st, st+cur)))
        #line = ' '.join([`num` for num in range(st, st+cur)])
        if cur == value: d=-1
        cur += d
        print(line)

 

L전자 개발자 코드 보완

print_range를 아래와 같이 변경하면 1~2초로 단축됨. (물론 재귀 깊이를 늘려놔야...)

def f(n):
    def f_util(start, width, n):
        if width > n:
            return
        print(' '.join(map(str, range(start, start + width))))
        f_util(start + width, width + 1, n)
        if width < n:
            print(' '.join(map(str, range(start, start + width))))
    f_util(1, 1, n)

 

N게임사 보완

 g()를 아래와 같이 변경하면 2초로 단축됨.

def g(n):
    first = n * (n + 1) // 2 + 1
    print(' '.join(map(str, range(first, first + n + 1))))
def f(n):
    for i in range(n):
        g(i)
    for i in range(n-2, -1, -1):
        g(i)

 

 

내 코드(보완) : n=4000일때 1초!!

def func(n):
    count = 1
    line = ''
    num_stack = [1]
    line_stack = []
    reverse = False

    while True:
        line = ''
        if (reverse):
            line = line_stack.pop()
        else:
            line = ' '.join(map(str, range(num_stack[-1], num_stack[-1] + count)))
            num_stack.append(num_stack[-1] + count)
            count += 1

        print(line)
        if (count > n):
            reverse = True
            num_stack = []
        else:
            line_stack.append(line)

        if (len(line_stack) == 0):
            break

 

 

보완코드로 보면 모두 n=4000일때 1~3초내로 들어온다.

 

현재 최고 기록(?)인 S사 개발자 iter모델과 내 보완 코드 성능 비교

n	S사 iter	내 코드 (수정)
8000	7초	약 3~4초
16000	35초	19초
32000	161초	93초

 

 

문자열이 다뤄지는 부분에서 (string splitting, concatenating, joining, formatting 등)

= iterable 객체에 대한 문자열 구성에서 크게 영향 받음을 확인했다. 

(iterable 객체를 다룰 때는 map을 적극 고려하자)

 

나야 뭐 일종의 꼼수(?)니까... 절반만 돌린셈이니..

근데 나처럼 생각한 사람이 아무도 없네? 그나마 S사 iter모델이 내 상상과 비슷하긴 했네.

 

 

그냥 재미삼아 비교해봤다.

N사 포털 개발자 람다식 효율이 어떨까 궁금했는데, (사람들이 전부 '좋아요' 누르길래 ㄷㄷㄷ)

가장 떨어지는 효율이었다. 

 

 

 

** 위 언급된 모든 코드에 대한 정확도/성능 검증 보장되지 않음 **

 

 

 

[참고]

iterable, iterator 차이?

https://stackoverflow.com/questions/1952464/in-python-how-do-i-determine-if-an-object-is-iterable

https://www.geeksforgeeks.org/python-difference-iterable-iterator/

https://stackoverflow.com/questions/6863182/what-is-the-difference-between-iterator-and-iterable-and-how-to-use-them

 

https://stackoverflow.com/questions/4435169/how-do-i-append-one-string-to-another-in-python

 

sys.getrecursionlimit(), sys.setrecursionlimit(limit)

https://docs.python.org/3/library/sys.html

 

lambda가 def에 비해 조금이라도 빠를 것 같다는데...

https://stackoverflow.com/questions/134626/which-is-more-preferable-to-use-in-python-lambda-functions-or-nested-functions

 

오! 람다가 느리네! 의견이 분분(?)한데, lambda + map + list 등의 콤비네이션은 피하는게 좋을 듯.

https://stackoverflow.com/questions/53568926/do-python-lambda-functions-help-in-reducing-the-execution-times

 

https://www.geeksforgeeks.org/python-map-function/

https://www.geeksforgeeks.org/programs-printing-pyramid-patterns-python/

https://pynative.com/print-pattern-python-examples/