[TIL] 파이썬 divmod / 스택 / 큐 / 집합

[주절주절]

여름 휴가 후 복귀! 👼

 

[Today I Learned]

# 파이썬 divmod

: 매개변수로 숫자 두개를 입력 받아 몫과 나머지를 튜플 형태로 반환하는 함수

a = divmod(10, 3)
print(a) >> (3,1)

 

# 스택

- 후입선출(LIFO)로 처리 되는 자료구조
- 파이썬의 리스트가 스택의 모든 연산을 지원한다.

- push : 요소를 컬렉션에 추가한다.
- pop : 제거되지 않은, 가장 최근에 삽입된 요소를 제거한다.

https://comlini8-8.tistory.com/82

↑이 때도 공부했었다.

 

+ 연결리스트를 이용한 스택 ADT 구현

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next

class Stack:
    def __init__(self):
        self.last = None

    def push(self, item):
        self.last = Node(item, self.last)

    def pop(self):
        item = self.last.item
        self.last = self.last.next

        return item

하지만 위에서도 말했듯이 리스트가 스택의 모든 연산을 지원하기 때문에 리스트를 바로 활용한다!

 

+ 괄호 검사

def is_valid(string):

    stack = []
    pair = {
        ')':'(',
        '}':'{',
        ']':'['
    }

    for s in string:
        if s not in pair: # 여는 괄호 - (, {, [
            stack.append(s) # = push

        elif not stack or pair[s] != stack.pop():
            return False
        
    return len(stack) == 0

 

# 큐

- 선입선출(FIFO)로 처리 되는 자료구조
- 역시 파이썬의 리스트가 큐의 연산을 지원한다. 하지만 리스트는 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 데크(Deque) 자료형을 사용해야 좋은 성능을 낼 수 있다.

 

# 파이썬 집합(set)

1) 선언

s = set()
s = set([1,3,5,7])
s = {1,2,3,4}

 

2) 원소 추가 ; add / update

s = {1,2,3,4}
s.add(10)

# s -> {1,2,10,3,4}

s = {1,2,3,4}
s.update([1,20,30])

# s -> {1,2,3,4,20,30}

보통 update는 여러 데이터를 한 번에 추가할 때 사용한다.

 

3) 원소 제거

s = {1,2,3,4}

s.remove(2)
3 s -> {1,3,4}

# s.remove(2) -> 에러

s = {1,2,3,4}

s.discard(2)
# s -> {1,3,4}

s.discard(2) # 에러나지 않음.
# s -> {1,3,4}

 

+ 중복 제거 후 사전식 순서로 정렬

def remove_n_sort(string):

    counter, seen, stack = collections.Counter(string), set(), []

    for s in string:
        counter[s] -= 1

        if s in seen:
            continue

        while stack and s < stack[-1] and counter[stack[-1]] > 0 : # and
            seen.remove(stack.pop())

        stack.append(s)
        seen.add(s)

    return ''.join(stack)

 

[질문 노트]

-