Python - 알고리즘 : 리스트, 딕셔너리

• 순서대로 저장하는 시퀀스이자 변경 가능한 목록(mutable list) 이다.
• 내부적으로는 동적 배열로 구현되어 있다.
• pop() 함수는 O(n) 이므로 주의한다.
• 데크(deque)와 같은 자료형을 사용해 성능을 높일 수 있다.

리스트 메소드의 시간 복잡도

# 리스트 메서드의 시간 복잡도
len(a) # 시간 복잡도 : O(1) - 전체 요소의 개수를 리턴한다.
a[i] # 시간 복잡도 : O(1) - 인덱스 i의 요소를 가져온다.
a[i:j] # 시간 복잡도 : O(k) - 인덱스 i 부터 j 까지 슬라이스의 길이만큼인 k 개의 요소를 가져온다. 이 경우 객체 1개에 대한 조회가 필요하므로 O(k) 이다.
elem in a # 시간 복잡도 : O(n) - elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n 만큼 시간이 소요된다.
a.count(elem) # 시간 복잡도 : O(n) - elem 요소의 개수를 리턴한다.
a.index(elem) # 시간 복잡도 : O(n) - elem 요소의 인덱스를 리턴한다.
a.append(elem) # 시간 복잡도 : O(1) - 리스트 마지막에 elem 요소를 추가한다.
a.pop() # 시간 복잡도 : O(1) - 리스트 마지막 요소를 추출한다. 스택의 연산이다.
a.pop(0) # 시간 복잡도 : O(n) - 리스트 첫 번째 요소를 추출한다. 큐의 연산이다. 이 경우 전체복사가 필요하므로 O(n)이다.
del a[i] # 시간 복잡도 : O(n) - 인덱스 i 의 요소를 삭제한다.
a.sort() # 시간 복잡도 : O(n log n) - 정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 O(n)에도 실행될 수 있다.
min(a), max(a) # 시간 복잡도 : O(n) - 최솟값/최댓값을 계산한다.
a.reverse() # 시간 복잡도 : O(n) - 뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다.

리스트의 특징

• 연속된 공간에 요소를 배치하는 배열의 장점과 다양한 타입을 연결해 배치하는 연결 리스트의 장점을 모두 갖고 있다.
• 리스트는 연결된 객체에 대한 포인터 목록으로 구현된다.
• 연결 리스트에 대한 포인터 목록을 배열 형태로 관리하고 있어 강력하다.
• 속도 면에서는 배열과는 다르게 객체에 대한 참조를 택했기 때문에 부가적인 작업이 필요하고 속도가 느릴 수 있다.

딕셔너리의 특징

• 키와 값으로 이루어진 자료형이다.
• 입력 순서가 유지되며 해시 테이블로 구현한다.
• 조회 및 삽입 연산 모두 O(1)의 시간 복잡도를 가진다.
• collections 모듈에서 Ordered(), defauldict(), Counter() 등을 제공한다.
• 딕셔너리는 dict() 함수나 중괄호 {} 를 사용하여 선언할 수 있다.
• 딕셔너리에 존재하지 않는 키를 조회하면 KeyError 가 발생하므로 예외 처리를 해주는 것이 좋다.
• 딕셔너리의 키와 값을 for 반복문을 꺼내올 수 있는데, items() 메서드를 사용하여 키와 값을 각각 가져올 수 있다.
• 딕셔너리에서 키는 del 로 삭제할 수 있다.

일반 딕셔너리

# dictionary
words = ['apple', 'bat', 'bar', 'atom', 'book'] # 단어가 담긴 배열, 리스트
by_letters = {} # 빈 객체, 딕셔너리

# words 안에 있는 word 를 돌면서
for word in words:
		# letter 를
    letter = word[0]
    if letter not in by_letters:
        by_letters[letter] = [word]
    else:
        by_letters[letter].append(word)

print(by_letters)
# {'a': ['apple', 'atom'], 'b': ['bat', 'bar', 'book']}
print(by_letters['c'])
# KeyError: 'c'

defaultdict

from collections import defaultdict
words = ['apple', 'bat', 'bar', 'atom', 'book']
by_letters = defaultdict(list)
for word in words:
    by_letters[word[0]].append(word)
print(by_letters)
# defaultdict(<class 'list'>, {'a': ['apple', 'atom'], 'b': ['bat', 'bar', 'book']})
print(by_letters['c'])
# []

알고리즘

Leetcode : Valid Palindrome

"""
Palindrome(팰린드롬 : 회문) 이란, 알파벳과 숫자가 아닌 다른 문장들을 제외한
상태에서 문장을 거꾸로 해도 같은 문자의 배열이 만들어지는 것을 말한다.
e.g. "Was it a rat I saw", "race car"

해당 알고리즘에서는 어떤 문자를 받았을 때 해당 문장이 팰린드롬인지 아닌지
판단하는 알고리즘을 구현한다.
"""

# Input: s = "A man, a plan, a canal: Panama"
# Input: s = " "
# Input: s = "race a car"

class Solution:
		# 함수는 실행되면 bool 형태로 값을 반환한다
    def isPalindrome(self, s: str) -> bool:
        strs = []
				# 입력 받은 string 문장의 문자 하나하나를 돌면서
        for char in s:
						# 알파벳인지 숫자인지 아니면 다른 형태인지 확인하고
            if char.isalnum():
								# 만약 참이면, lower case 로 바꾼다
								# 그리고 미리 만들어둔 빈 배열 strs 에 추가한다.
                strs.append(char.lower())
				# strs 에서 하나씩 빼는데, 길이가 1이하 그니까 전부 뺼 떄까지 반복
        while len(strs) > 1:
						# 만약 맨앞에서 뺀거와 맨 뒤에서 뺀게 같지 않으면 ?
            if strs.pop(0) != strs.pop():
								# False
                return False
				# 빼낸 글자가 모두 같으면 앞뒤로 똑같다고 하니까 True
        return True

class Solution5:
    def isPalindrome(self, s: str) -> bool:
        # i starts at beginning of s and j starts at the end
				# i 능 앞쪽부터 시작하고 j 는 맨 뒤부터 시작
        i, j = 0, len(s) - 1
        # While i is still before j
				# i 가 j 와 같아질때 까지 
        while i < j:
            # If i is not an alpha-numeric character then 
						# advance i
            if not s[i].isalnum():
                i += 1
            # If j is not an alpha-numeric character then 
						# advance i
            elif not s[j].isalnum():
                j -= 1
            # Both i and j are alpha-numeric characters 
						# at this point so if they do not match return 
            # the fact that input was non-palendromic
            elif s[i].lower() != s[j].lower():
                return False
            # Otherwise characters matched and we should look
						# at the next pair of characters
            else:
                i, j = i + 1, j - 1
        # The entire stirng was verified and we return 
				# the fact that the input string was palendromic
        return True

Leetcode : Reverse String

# Reverse String
"""
리스트의 형태로 저장된 s 변수의 값을 뒤집어라
단, 여기서 변수를 새로 정의하지 말고 바로 바뀌게 하라
"""
# Input: s = ["h","e","l","l","o"]
# Input: s = ["H","a","n","n","a","h"]
class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
        """
        Do not return anything, modify s in-place instead.
        """

class Solution2:
    def reverseString(self, s: List[str]) -> None:
        s[:] = reversed(s)
        """
        Do not return anything, modify s in-place instead.
        """

Leetcode : Reorder Data in Log Files

# Reorder Data in Log Files
"""
로그 앞부분을 식별자로
문자로 구성된 로그는 숫자보다 앞으로 정렬해라
식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순 정렬한다.
숫자 로그는 입력 순서대로 진행한다.
"""
# Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
# Input: logs = ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
class Solution:
		# 문자로그는 공백으로 나누었을 때 두 번째 요소가 문자열이므로, 이를 기준으로 구분한다.
		# 숫자로그는 각각 따로 리스트에 저장하고 문자 로그는 문자열 기준으로 정렬한다.
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        letter_logs = []
        digit_logs = []

        for log in logs:
            if log.split()[1].isdigit():
                digit_logs.append(log)
            else:
                letter_logs.append(log)

        print(digit_logs)
        print(letter_logs)

        letter_logs.sort(key=lambda x: (x.split()[1:], x.split()[0]))
        return letter_logs + digit_logs

class Solution2:
		# 람다식을 사용하지 않고 custom_sort 함수를 정의해 정렬에 사용
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        digits = []
        letters = []
        for log in logs:
            if log.split()[1].isdigit():
                digits.append(log)
            else:
                letters.append(log)
        letters.sort(key=custom_sort)
        return letters + digits

def custom_sort(log: str) -> Tuple[str]:
    identifier, content = log.split(" ", 1)
    return content, identifier

Leetcode : Most Common Word

# Most Common Word
"""
금지된 단어를 제외한 단어 중 가장 많이 나온 단어를 반환하라
"""
# Input: paragraph = "a.", banned = []
# Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
import re
import collections

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        words = [word for word in re.sub(r'[^\\w]', ' ', paragraph).lower().split() if word not in banned]
        counts = collections.Counter(words)
        return counts.most_common(1)[0][0]

import re

class Solution2:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        # convert to lower case and split string into words by spaces and punctuation
        a = re.split(r'\\W+', paragraph.lower())

        # make new list consisitng of words not in banned list (remove banned words)
        b = [w for w in a if w not in banned]

        # return value that counted max times in the new list
        return max(b, key=b.count)

import re

class Solution3:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        my_dict = defaultdict(int)
        # split string into list ignoring cases and punctuation
        par = re.split("[" + string.punctuation + " " + "]+", paragraph.lower())
        # keep counts of words in dict and keep track of most frequent
        max_count = 0
        max_word = ""
        for word in par:
            if word not in banned:
                my_dict[word] += 1
                if my_dict[word] > max_count:
                    max_count = my_dict[word]
                    max_word = word
        return max_word

Leetcode : Group Anagrams

# Group Anagrams
"""
같은 알파벳을 가지고 있는 조합을 찾아라
"""
# Input: strs = ["eat","tea","tan","ate","nat","bat"]
# Input: strs = [""]
# Input: strs = ["a"]

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = {}
        for word in strs:
            sorted_word = "".join(sorted(word))
            print(sorted_word)
            # aet
            # aet
            # ant
            # aet
            # ant
            # abt
            if sorted_word in anagrams:
                anagrams[sorted_word].append(word)
            else:
                anagrams[sorted_word] = [word]

        return anagrams.values()
    # [["eat","tea","ate"],["tan","nat"],["bat"]]

class Solution2:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        h = {}
        for word in strs:
            sortedWord = ''.join(sorted(word))
            if sortedWord not in h:
                h[sortedWord] = [word]
            else:
                h[sortedWord].append(word)
        final = []
        for value in h.values():
            final.append(value)
        return final

Sorting 심화

# insert
def insertion_sort(arr, start, end):
    for i in range(start + 1, end + 1):
        key_item = arr[i]
        j = i - 1
        while j >= start and arr[j] > key_item:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key_item

# merge
def merge(arr, start, mid, end):
    left = arr[start:mid+1]  # Include mid in left partition
    right = arr[mid+1:end+1]  # Start from mid + 1

    i = 0
    j = 0
    k = start

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

# timsort
def timsort(arr):
    min_run = 2
    n = len(arr)

    for i in range(0, n, min_run):
        end = min((i + min_run - 1), (n - 1))  # Ensure we do not exceed array bounds
        insertion_sort(arr, i, end)

    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            mid = min((start + size - 1), (n-1))
            end = min((start + size * 2 - 1), (n-1))
            merge(arr, start, mid, end)
        size *= 2

    return arr

a = ['f', 'g', 'h', 'z', 's', 'b', 'c', 'd']

print(timsort(a))

Tip

• isalnum()는 문자열이 알파벳 또는 숫자로만 구성되어 있는지 확인하는 파이썬 문자열 메서드이다. 이 메서드는 문자열에 문자와 숫자만 포함되어 있으면 True를 반환하고, 그렇지 않으면 False를 반환한다.
• **deque**는 파이썬의 collections 모듈에서 제공하는 자료구조이다. deque는 큐(queue)와 스택(stack)의 특성을 모두 가지고 있으며, 양쪽 끝에서 빠르게 요소를 추가하거나 제거할 수 있는 자료구조이다.