직각삼각형 출력하기

문제

 

 

내 풀이

 

# "*" * repeat 문자열 곱셈 분석(ex. repeat = 4인 경우) :

1. 새로운 길이 4짜리 문자열을 메모리에 할당 → O(1)

2. "*"을 4번 복사해서 채운다. → O(4)

즉, "*" * n은 O(n) 연산 (Big-O 표기법에서 가장 큰 차수만 남기고 나머지는 무시한다. O(1) + O(n) = O(n))

 

 

# 분석 : 

각 반복문에서 repeat의 값만큼 별을 출력(print)하므로, 실행되는 총 연산 횟수는 다음과 같다.

• repeat = 1  →  O(1)
• repeat = 2  →  O(2)
• ...
• repeat = n  →  O(n)

print() 자체는 O(1)이지만, "*" * repeat 문자열을 생성하는 과정이 O(n)만큼 시간복잡도를 가지는데, for문으로 repeat이 1부터 n까지 변하면서 O(n²) 시간이 걸린다.

 

 

#  결론 :

즉, 총 출력 횟수는 1+2+3+4+...+n = (n * (n + 1)) / 2 = O(n²) 이다.

 

 

 

 

# 최적화 방법 :

inputValue = int(input())

if 1 <= inputValue <= 10:
    print("\n".join("*" * repeat for repeat in range(1, inputValue + 1)))

문자열을 한 번에 만들어서 출력하는 방식이다.

• Generator Expression 방식 통해 ["*", "**", "***", ...] 리스트를 먼저 O(n) 시간에 생성
• "\n".join(...)을 한 번만 실행해서 출력하니까, 전체 시간 복잡도는 O(n)으로 줄어든다.