파이썬으로 풀어보는 백준 2447번: 별 찍기 - 10

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

 

내 풀이:

N=int(input())
k=1
TF=N
while True:
    if TF//3==1:
        break
    else:
        TF=TF//3
        k+=1
 
result=[["*"]*3**k for i in range(3**k)]
 
for p in range(k):
    for q in range(3**k):
        for r in range(3**k):
            if (3**(p)) <= (q%(3**(p+1))) < (2*(3**(p))) and (3**(p)) <= (r%(3**(p+1))) < (2*(3**(p))):
                result[q][r]=" "
 
for i in range(3**k):
    for j in range(3**k):
        print(result[i][j], end='')
    print("")

시간 초과

조건문이 16열, 가장 안쪽 for문에 들어있기 때문에 빈칸을 구분해주는 행위를 N번이나 반복하게 된다. 때문에 시간 초과가 난 것으로 판단된다.

N = int(input())
k = 1
TF = N
while True:
    if TF // 3 == 1:
        break
    else:
        TF = TF // 3
        k += 1
 
result = [["*"] * 3 ** k for i in range(3 ** k)]
 
for p in range(k):
    condition = [i for i in range(N) if (i // 3 ** p) % 3 == 1]
    for q in condition:
        for r in condition:
            result[q][r] = " "
 
for i in range(3 ** k):
    for j in range(3 ** k):
        print(result[i][j], end='')
    print("")

3052ms

시간을 줄이기 위해 조건문을 가장 바깥쪽 for문으로 옮기고 조건에 해당하는 리스트를 새로 만들어 하위 for문의 범위도 줄였다. 또한 조건문의 표현 방식을 값의 범위에서 나머지의 형태로 표현하면서 간결해졌다.

 

wider93님 풀이:

def concatenate(r1, r2):
    return [''.join(x) for x in zip(r1, r2, r1)]
 
def star10(n):
    if n == 1:
        return ['*']
    n //= 3
    x = star10(n)
    a = concatenate(x, x)
    b = concatenate(x, [' '*n]*n)
 
    return a + b + a
 
print('\n'.join(star10(int(input()))))

64ms

내 코드와 시간 차이가 거의 50배가 차이 나는 이 코드는 심지어 코딩조차 짧다. 알고리즘이 얼마나 중요한가를 뼈저리게 느끼는 순간이다.