[Python] 알고리즘 기초: 공간 복잡도

• 공간 복잡도란? 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
• 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것
• 입력값이 늘어나도 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘!

---

 

▼ 시공간 복잡도를 이해하기 위한 알파벳 찾기 문제 

문제 설명 
a 부터 z 까지, 주어진 문자열에서 알파벳이 포함되어 있을 경우 처음 등장하는 인덱스를 반환하는 프로그램을 작성하세요. 포함되어있지 않을 경우 -1을 반환하면 됩니다.

 

 

※  아스키(ascii) 코드 다루기

import string

# 1. 알파벳을 바로 꺼내오는 방법
print(string.ascii_lowercase)

# 2. ord 연산
print(ord('a'), ord('A'), ord('@'))  # 97 65 64

# 3. range
for i in range(10):
    print(i)

 

▼  알파벳 찾기

import string


def get_idx_naive(word):
		# O(N^2)
    result = [-1]*len(string.ascii_lowercase)
    for i in range(len(word)):
        char = word[i]
        for j in range(len(string.ascii_lowercase)):
            lo = string.ascii_lowercase[j]
            if result[j] == -1 and char == lo:
                result[j] = i
    return result


def get_idx(word):
    # O(N)
    result = [-1]*len(string.ascii_lowercase)
    for i in range(len(word)):
        idx = ord(word[i]) - 97
        if result[idx] == -1:
            result[idx] = i
    return result


print(get_idx_naive('sparta'))
print(get_idx('sparta'))

 

 

 

(# 문제 풀이 작성 중 ..)