암호 해독

문제

 

 

 

# 내 풀이

내 풀이

 

 

# 풀이

시간 복잡도

• for a in cipher: 루프가 cipher의 길이 n만큼 실행됨.
• 루프 내부에서 sum을 1 증가시키는 연산은 O(1)
• if sum % code == 0: 조건문은 O(1)
•  Python의 문자열은 **불변(immutable)** , "+=" 연산은 매번 새로운 문자열을 생성하고 기존 내용을 복사하는 과정이 필요하다.
  • ex)
    • 첫 번째 s += "a" → "a" (새로운 메모리 할당)
    • 두 번째 s += "b" → "ab" (새로운 메모리 할당, "a" 복사)
    • 세 번째 s += "c" → "abc" (새로운 메모리 할당, "ab" 복사)
  • ➡ 전체적으로 O(n2)의 시간 복잡도가 발생

 

 

 

공간 복잡도

• sum과 answer 변수는 추가적인 저장 공간을 차지하지만, answer는 최종적으로 저장되는 문자 수에 비례하여 증가.
• 최악의 경우 answer가 cipher의 길이 n만큼 커질 수 있음.

따라서 공간 복잡도는 O(n)

 

 

 

 

# 최적화

def solution(cipher, code):
    answer = []
    for i in range(code - 1, len(cipher), code):
        answer.append(cipher[i])
    
    return ''.join(answer)

 

시간 복잡도

• for 루프: O(n/code) ≈ O(n)
• append(): 평균적으로 O(1) (리스트의 끝에 추가하는 연산)
• join(): O(n) (리스트의 요소를 하나의 문자열로 합치는 연산)

➡ 최적화 후 시간 복잡도: O(n) (이전 O(n2)보다 개선됨)

공간 복잡도

• answer 리스트에 선택된 문자만 저장하므로 최악의 경우 O(n)
• 최종적으로 join()을 수행해 문자열을 반환하므로, 공간 복잡도는 여전히 O(n)